boj 1197 - 최소 스패닝 트리(MST, kruskal)

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

MST를 구할 때 사용하는 알고리즘은 프림, 크루스칼 알고리즘이 있다.

(V, E)가 각각 그래프의 노드, 엣지의 갯수 일때

노드를 기준으로 MST를 찾아나가는 프림 알고리즘은 은 복잡도가 O(V*E) = O(V^3)이고,

엣지를 기준으로 Disjoint set을 합치면서 사이클이 생기지 않았는지 검사하는 union-find 알고리즘을 이용하면 복잡도가 O(ElogE)이기 때문에 대체로 더 빠르다. 이 문제의 풀이를 기준으로 union-find 알고리즘을 공부하면 좋을 것 같다.

간선들을 비용을 기준으로 오름차순으로 정렬해놓고, 순차적으로 하나씩 find 함수를 통해서 root노드가 같은지 여부를 검사한다.

만약 루트노드가 다르다면 두 트리를 합친다(Union), 같다면 이미 같은 트리 내에 있으므로 합치지 않는다.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// MST - kruskal 알고리즘, union-find

struct Edge {
    int from, to, cost;
    bool operator<(const Edge& other) const {
        return cost < other.cost;
    }
};

vector<int> p(10001);
int Find(int x) {
    if (x == p[x])
        return x;
    else
        return p[x] = Find(p[x]);
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    p[x] = y;
}

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

    int v, e;
    cin >> v >> e;
    for (int i = 1; i <= v; ++i) {
        p[i] = i;
    }

    vector<Edge> edgeList(e);
    for (int i = 0; i < e; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        edgeList[i] = {x, y, c};
    }
    sort(edgeList.begin(), edgeList.end());  // 오름차순으로 간선 정렬

    int ans = 0;
    for (int i = 0; i < e; ++i) {
        Edge edge = edgeList[i];
        int x = Find(edge.from);
        int y = Find(edge.to);
        if (x != y) {
            Union(edge.from, edge.to);
            ans += edge.cost;
        }
    }

    cout << ans;
    return 0;
}