백준 1197

 

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

1197번: 최소 스패닝 트리

최소 스패닝 트리 (MST, Minimum Spanning Tree)

① 프림 알고리즘 (노드 기준)

② 크루스칼 알고리즘 (엣지 기준)

 

필요한 자료구조

1. 벡터: 그래프 저장 (인접 리스트)

2. 배열: 부모 노드 저장 (Union-Find)

3. 우선순위 큐: 엣지 저장

 

01234567

 

#include <iostream>
#include <queue>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
struct Node {
    int a;
    int b;
    int weight;
};
struct cmp {
    bool operator()(Node a, Node b) {
        return a.weight > b.weight;
    }
};
priority_queue<Node, vector<Node>, cmp> pq;
int v, e, parent[10001], ans;
int find(int x) {
    if (x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}
void unionSet(int a, int b) {
    int x = find(a);
    int y = find(b);
    if (x > y)
        parent[x] = parent[y];
    else
        parent[y] = parent[x];
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> v >> e;
    rep(i, v)
        parent[i] = i;
    rep(i, e) {
        int a, b, c;
        cin >> a >> b >> c;
        pq.push({ a,b,c });
    }
    while (!pq.empty()) {
        Node now = pq.top(); pq.pop();
        int a = find(now.a);
        int b = find(now.b);
        if (a == b) continue;
        unionSet(a, b);
        ans += now.weight;
    }
    cout << ans;
}