예제 : 1197번 '최소 스패닝 트리'

1197번: 최소 스패닝 트리

개념

[알고리즘] 최소 신장 트리

크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전

최소 스패닝 트리(minimal Spanning Tree : MST)를 구현하는 알고리즘은 두 가지 가 있다.

• Kruskal 알고리즘
• Prim 알고리즘

이 중에서 Kruskal알고리즘에 대해서 설명한다.

동작 과정

1. 모든 간선들의 가중치를 오름차순으로 정렬한다. 힙을 쓰거나 pair를 sort() 하자.

2. 힙에서 (가중치가 가장 작은) 간선을 하나 뽑는다. 뽑은 간선의 두 노드가 연결되어 있지 않다면 연결한다. 여기서 find_parent 로 검사하고 union_edge 으로 연결해주면 된다.

   parent[] 라는 배열을 둘 건데 이 배열은 서로 다른 두 노드의 부모가 같은지 판별하는데 쓰인다. 두 노드의 부모가 같다면 두 노드는 연결되어 있다는 뜻이고, 두 노드의 부모가 다르다면 연결되어 있지 않다는 뜻이다.

   find_parent의 과정에서 부모의 부모를 끝까지 찾아가므로, 굳이 따지자면 부모가 같은게 아니라 조상이 같다는 표현이 더 정확한것 같을지도 모르겠다.

   parent[] 배열은 처음에 자기 자신으로 초기화 된다. 예를 들어 parent[i] = i 으로 초기화 된다.

3. 위 과정을 반복한다.

C++

1197번 '최소 스패닝 트리'

아래에는 PriorityQueue를 사용했지만 vector를 사용해도 된다.

#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

class edge {
   public:
    int from;
    int to;
    int weight;
    edge(int f, int t, int w) {
        from = f;
        to = t;
        weight = w;
    }
};
struct cmp {
    bool operator()(edge& a, edge& b) {
        return a.weight > b.weight;
    }
};

int v, e;
priority_queue<edge, vector<edge>, cmp> pq;
int parent[10001];

int find_parent(int x) {
    if (parent[x] == x)
        return x;
    else
        return parent[x] = find_parent(parent[x]);
}
bool same_parent(int x, int y) {
    int a = find_parent(x);
    int b = find_parent(y);
    if (a == b)
        return true;
    else
        return false;
}
void union_set(int x, int y) {
    int a = find_parent(x);
    int b = find_parent(y);
    if (a != b) parent[b] = a;
}

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

    cin >> v >> e;
    int f, t, w;
    for (int i = 0; i < e; i++) {
        cin >> f >> t >> w;
        pq.push(edge(f, t, w));
    }

    // init Parent
    for (int i = 1; i <= v; i++) {
        parent[i] = i;
    }

    int weight_sum = 0;

    // Kruskal
    while (!pq.empty()) {
        edge cur_edge = pq.top();
        pq.pop();
        if (!same_parent(cur_edge.from, cur_edge.to)) {
            union_set(cur_edge.from, cur_edge.to);
            weight_sum += cur_edge.weight;
        }
    }

    // // check
    // for (int i = 1; i <= v; i++) {
    //     cout << parent[i] << " -> " << i << '\\n';
    // }

    cout << weight_sum << '\\n';
}