[백준 1647] 도시 분할 계획

 

 심플한 MST(Minimum Spanning Tree, 최소 신장 트리) 문제다. 간선의 수가 최대 1,000,000으로 그리 크지 않아서 O(E logE)인 Kruskal 알고리즘으로 해결했다.

 Kruskal 알고리즘을 사용하기 위해서는 경로 집합에 해당 간선이 포함되어 있는지를 확인해야 하므로, Union-Find 알고리즘을 구현해서 빠르게 판별할 수 있도록 했다.

 일반적인 MST와 조금 다른게 있다면 두 개의 MST를 만들어야 한다는 점인데, 이는 Union의 수가 두 개일때까지만 Kruskal 알고리즘을 진행하는 것으로 구현할 수 있다.

 전형적인 MST 유형인데다, 디테일한 구현 요소도 없어서 그 외에는 크게 신경쓸 건 없었던 것 같다.

 

#include <iostream>
#include <queue>

using namespace std;

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

int root[100000];

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

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

    if(x<y) {
        root[y] = x;
        return true;
    } else if(x>y) {
        root[x] = y;
        return true;
    } else {
        return false;
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    int n, m, start, end, cost;
    cin >> n >> m;

    priority_queue<edge> pq;

    for(int i=0; i<n; i++) {
        root[i] = i;
    }

    for(int i=0; i<m; i++) {
        cin >> start >> end >> cost;
        pq.push({-cost, {start, end}});
    }

    int minCost = 0;
    int unionNum = n;

    while(!pq.empty() && unionNum > 2) {
        edge e = pq.top();
        pq.pop();

        if(makeUnion(e.second.first, e.second.second)) {
            unionNum--;
            minCost-=e.first;
        }
    }

    cout << minCost;
}