1647번: 도시 분할 계획

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

입력받은 그래프를 두 개의 트리로 만드는 문제이다. 이 때 만들어진 두 트리의 가중치의 합을 최소화해야 하므로, 이 문제는 최소 스패닝 트리 문제라고 할 수 있다. 

- 크루스칼 기법

크루스칼 기법을 사용하면서 트리의 개수를 추적하다가, 트리의 개수가 2개 이하로 내려가는 순간 기법을 멈추고 가중치의 총합을 출력한다.

후술할 프림 알고리즘과 마찬가지로 트리를 완성한 뒤 트리의 가중치에 최대 에지 가중치를 뺀 값을 출력해도 되지만, 이 방법은 트리의 개수를 추적하는 방법과 완벽히 똑같이 작동하면서, 거기에 추가로 더 작업을 진행해야 하므로 효율이 떨어진다.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, pair<int, int>> edge;

#define MAX_N 100000
#define _C first
#define _A second.first
#define _B second.second

// N: 주어진 조건에서 노드 수
// parent[i]:각 노드가 속한 트리에서 노드의 부모, 혹은 루트 노드
int N, M;
int parent[MAX_N + 1] = { 0, };
// 에지를 저장할 공간
vector<edge> v;

// 입력받은 노드를 포함하는 트리의 루트를 재귀적으로 탐색하여 반환
int root(int node) {
    if (parent[node] == node || !parent[node]) return node;
    return root(parent[node]);
}

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // M: 에지의 수
    // cnt: 현재 에지들이 이루는 트리의 수, ans: 모든 트리의 가중치의 합
    int M, cnt, ans = 0, A, B, C;

    // 노드와 에지의 수를 입력받은 뒤
    cin >> N >> M;
    
    // 트리의 수를 노드의 수로 설정
    cnt = N;
    // 에지의 집합 v의 크기를 정의
    v = vector<edge>(M);

    // 각 에지를 입력받은 뒤 cost 순으로 정렬
    for (edge &e : v) cin >> e._A >> e._B >> e._C;
    sort(v.begin(), v.end());

    // cost가 작은 에지부터 순서대로
    for (edge e : v) {
        // 트리의 수를 2개 미만으로 줄였다면 루프를 탈출
        if (cnt <= 2) break;
        
        // 현재 에지의 두 노드를 각 노드가 속한 트리의 루트로 치환
        // 두 노드가 같은 트리에 속해 있다면 continue
        A = root(e._A);
        B = root(e._B);
        if (A == B) continue;

        // 서로 다른 트리를 에지로 연결했으므로 cnt를 1 줄인 뒤
        cnt--;
        // ans에 현재 에지의 가중치를 더하고
        ans += e._C;
        // 두 루트 노드 중 값이 더 작은 노드를 루트 노드로 설정
        parent[(A > B ? A : B)] = (A < B ? A : B);
    }

    // 가중치의 합을 출력
    cout << ans << '\n';

    return 0;
}

-프림 기법

최소 스패닝 트리를 만들면서 사용된 에지의 가중치의 최댓값을 따로 저장하고, 트리의 가중치에 최대 에지 가중치를 뺀 값을 출력하면 된다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> edge;

#define MAX_N 10
#define _cost first
#define _node second

bool visit[MAX_N + 1];

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // N, M: 그래프의 노드와 에지의 개수
    // max: 최소 스패닝 트리에 쓰인 가중치의 최댓값
    // sum: 최소 스패닝 트리의 가중치의 총합
    // A, B, C: 노드 A, B를 잇고 가중치가 C인 에지
    int N, M, max = 0, sum = 0, A, B, C;
    priority_queue<edge, vector<edge>, greater<edge>> q;
    vector<edge> v[MAX_N + 1];

    // 그래프를 입력받은 뒤
    cin >> N >> M;
    while (M--) {
        cin >> A >> B >> C;
        v[A].push_back({C, B});
        v[B].push_back({C, A});
    }

    // 1번 노드를 최소 스패닝 트리의 루트 노드로 설정
    // 1번 노드를 방문한 뒤 1번 노드와 연결된 에지를 모드 q에 push
    visit[1] = true;
    for (edge e : v[1]) q.push(e);

    // 모든 접근 가능한 에지에 대해
    while (!q.empty()) {
        // q에서 에지를 하나 가져온 뒤
        edge e = q.top();
        q.pop();

        // 에지와 연결된 노드에 방문한 적 있다면 continue
        if (visit[e._node]) continue;
        
        // 트리의 가중치에 에지의 가중치를 더한 뒤
        sum += e._cost;
        // 가중치의 최댓값을 갱신한 후
        if (max  < e._cost) max = e._cost;
        // 에지에 연결된 노드에 방문
        visit[e._node] = true;
        // 방문한 노드에 연결된 모든 접근 가능한 에지를 q에 push
        for (auto e_ : v[e._node]) if (!visit[e_._node]) q.push(e_);
    }

    // 트리의 가중치의 합에서 트리에서 가장 큰 에지의 가중치를 뺀 값을 출력
    cout << sum - max << '\n';

    return 0;
}