백준 1922번 - 네트워크 연결

백준 1922번 - 네트워크 연결

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

문제

• 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다.

• 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다.

• 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다.

  • (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

• 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다.

• 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력

• 첫째 줄에 컴퓨터의 수(1<=N<=1000)가 주어진다.

• 둘째 줄에는 연결할 수 있는 선의 수(1<=M<=100,000)가 주어진다.

• 셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다.

  • 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c만큼 든다는 것을 의미한다.

출력

• 모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

접근

• 최소 스패닝 트리(MST) 문제이다.

• Disjoint-Set 구조(Find-Union)를 활용하여 Kruskal 알고리즘을 구현한다.

Kruskal 알고리즘

• 간선들을 Weight를 기준으로 오름차순으로 정렬한다.

• Weight가 가장 낮은 간선부터 차례대로 연결하여 트리를 만든다.

• 간선을 연결할 때 트리가 사이클을 형성하지 않도록 한다.

  • find(u) == find(v) 인 경우, 사이클이 생긴다.

• 유니온

  • 정점들을 연결할 때, 트리의 깊이가 깊어지지 않도록, Union by rank 방법으로 항상 작은 트리를 큰 트리의 루트에 붙이도록 한다.

  • find 연산을 수행할 때마다 트리의 구조를 평평하게 만들어 경로를 압축한다. parent[v] = find(parent[v])

C++ Code

#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
​
int n, m;
priority_queue<tuple<int, int, int>> edges;
int parent[1001] = { 0, };
int r[1001] = { 0, };
int ans = 0;
​
void makeset(int v) {
    parent[v] = v;
    r[v] = 0;
}
​
int find(int v) {
    if (parent[v] == v) {
        return v;
    }
​
    return parent[v] = find(parent[v]);
}
​
void union_node(int a, int b) {
    int root_a = find(a);
    int root_b = find(b);
​
    if (r[root_a] < r[root_b]) {
        parent[root_a] = root_b;
    }
    else if (r[root_b] > r[root_b]) {
        parent[root_b] = root_a;
    }
    else {
        parent[root_b] = root_a;
        r[root_a]++;
    }
}
​
int main(void) {
    scanf("%d", &n);
    scanf("%d", &m);
​
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        edges.push(make_tuple(-w, a, b));
    }
    
    for (int i = 1; i <= n; i++) {
        makeset(i);
    }
​
    while(!edges.empty()){
        auto edge = edges.top();
        
        int w = -get<0>(edge);
        int a = get<1>(edge);
        int b = get<2>(edge);
​
        if (find(a) != find(b)) {
            union_node(a, b);
            ans += w;
        }
​
        edges.pop();
    }
​
    printf("%d\n", ans);
​
    return 0;
}
​