[백준 1922] 네트워크 연결

 

 최소 스패닝 트리 문제. 가장 심플한 형태의 MST 문제라서 포스팅을 작성하지 않으려다가, 그래도 MST를 처음 접하는 사람들에겐 연습하기 좋은 문제인 것 같아서 들고 왔다.

 

 각각의 컴퓨터를 노드로 생각하고, 무방향 가중치 그래프의 부분 그래프로 모든 노드가 연결되도록 했을 때 그 간선 비용의 총합이 최소가 되어야 한다. 이런 유형의 문제는 대부분 MST 문제인 경우가 많다. MST는 Kruskal 알고리즘이나 Prim 알고리즘으로 해결하게 되는데 간단하게 차이를 정리하면 아래와 같다.

 

Kruskal 알고리즘

- 모든 간선을 비용 기준으로 정렬하여, 사이클이 되지 않도록 간선을 하나씩 스패닝 트리에 추가하는 방법.

- 사이클에 대한 판정은, 새로 추가하려는 간선의 두 노드가 스패닝 트리 내에서 이미 하나의 연결 그래프에 속한 경우이다. 이는 Disjoin Set(분리 집합)을 통해 쉽게 구현할 수 있다.

- 따라서 전체 시간 복잡도는, 간선 정렬이 O(E log E), 간선을 추가하며 사이클을 검사하는(Union-Find) 시간이 O(E * a(V)) (a는 아커만 함수의 역함수로, a(V)는 상수시간에 근사)에 해당하므로, O(E log E)에 근사한다.

 

Prim 알고리즘

- 하나의 노드에서 출발해, 스패닝 트리를 만들어 나가는 방법.

- 노드가 추가될 때마다, 우선순위 큐에 해당 노드에 연결된 간선들을 추가하고 연결되지 않은 노드로 향하는 최소 비용 간선을 찾아낸다.

- 다익스트라 알고리즘과 유사하다고 할 수 있으며, 전체 시간 복잡도는, 간선 정보를 우선순위에 넣고 빼는 시간이 O(log V)이고, 그 과정이 초기화 때 V번, 스패닝 트리 형성 과정에서 E번 실행될 수 있다. 따라서 O((V+E) log V)에 근사한다.

- 우선순위 큐를 사용하지 않고 인접 행렬을 사용할 수도 있는데, 이 경우에는 O(V^2)에 해당한다.

 

 위와 같은 특징을 생각할 때, Kruskal 알고리즘은 희소 그래프에서 유리하고, Prim 알고리즘은 밀집 그래프에서 유리함을 추측할 수 있다. 나는 MST 문제에서 일반적으로 Kruskal 알고리즘을 많이 사용하는 편이다.

 이번 문제도 Disjoint Set 및 우선순위 큐(위에선 정렬을 사용한다고 썼으나, 우선순위 큐를 써도 무방하다)를 통해 Kruskal 알고리즘을 구현해 풀었고, 문제를 보니 입력받는 a, b 값이 동일할 수도 있다고 명시되어 있어서 이를 따로 처리해 주었다. a, b 값이 동일하다면 노드 본인에게 향하는 간선이므로, MST를 만드는 데 전혀 영향을 주지 않으므로 처음부터 간선 집합에 넣지를 않았다. 

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

using namespace std;

vector<int> root;

int find(int n) {
    if(root[n]==n) return n;

    return root[n]=find(root[n]);
}

bool makeUnion(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if(rootX==rootY) {
        return false;
    } else if(rootX<rootY) {
        root[rootY] = rootX;
    } else {
        root[rootX] = rootY;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, a, b, c;
    cin >> n >> m;

    for(int i=0; i<=n; i++) {
        root.push_back(i);
    }

    auto cmp = [](const pair<pair<int, int>, int>& l, const pair<pair<int, int>, int>& r) {
        return l.second>r.second;
    };
    priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int> >, decltype(cmp)> pq(cmp);

    while(m--) {
        cin >> a >> b >> c;

        if(a!=b) pq.push({{a, b}, c});
    }

    int edgeNum = 0;
    int costSum = 0;
    while(edgeNum<n-1) {
        auto nodeP = pq.top().first;
        int cost = pq.top().second;
        pq.pop();

        if(makeUnion(nodeP.first, nodeP.second)) {
            edgeNum++;
            costSum += cost;
        }
    }

    cout << costSum;
}