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

문제

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력

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

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

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

출력

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

예제 입출력

• 예제 입력 1

6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
3 5 11
4 5 3
4 6 8
5 6 8

• 예제 출력 1

23

Solution

두 가지 방법이 있다. 이번 포스팅에서는 Kruskal Algorithm을 활용해보겠다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100001
using namespace std;

int N, M;
int Parent[MAX];

int getParent(int num){
    if(num == Parent[num]) return num;
    return Parent[num] = getParent(Parent[num]);
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a != b) Parent[a] = b;
}

bool findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    else return false;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    int result = 0;
    vector<pair<int, pair<int, int>>> vec(M);
    for(int i = 0; i < M; i++){
        int src, dst, cost;
        cin >> src >> dst >> cost;
        vec[i] = {cost, {src, dst}};
    }
    for(int i = 1; i <= N; i++) Parent[i] = i;
    sort(vec.begin(), vec.end());
    for(int i = 0; i < M; i++){
        int cost = vec[i].first;
        int src = vec[i].second.first;
        int dst = vec[i].second.second;
        if(!findParent(src, dst)){
            result += cost;
            unionParent(src, dst);
        }
    }
    cout << result << '\n';
}

Kruskal Algorithm은 다음과 같다.

1. 모든 간선들의 가중치를 오름차순으로 정렬한다.
2. 가중치가 가장 작은 간선을 선택한다.
3. 2에서 선택한 간선이 연결하려는 2개의 노드가 아직 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
4. 위의 과정을 반복한다.

확인할 수 있다시피 Kruskal Algorithm은 가중치가 가장 작은 간선들을 선택해서 그 간선 간에 노드들이 연결되지 않았다면 연결시켜주는 알고리즘이다.
이 문제에서 Kruskal Algorithm을 사용한 이유는 간단하다. 최소한의 비용으로 모든 컴퓨터들을 연결해야 하기 때문이다. Union Find 알고리즘을 활용해야 하므로 각 노드들의 Parent를 저장하고 있는 배열 또한 선언 해 둔다.

int result = 0;
vector<pair<int, pair<int, int>>> vec(M);
for(int i = 0; i < M; i++){
    int src, dst, cost;
    cin >> src >> dst >> cost;
    vec[i] = {cost, {src, dst}};
}
for(int i = 1; i <= N; i++) Parent[i] = i;
sort(vec.begin(), vec.end());

선수 작업으로 모든 간선들의 가중치를 정렬하는 과정이다. 벡터의 구조는 비용, 출발지, 목적지 이다. 위의 예시와 같이 pair를 통해 묶어도 되고 Tuple로 해도 아무 상관없다. 어차피 구현하는 사람 마음이니까 이 부분은.

이제 모든 간선들을 뒤져가면서 만약 두 노드 간에 Parent 관계가 아니라면 unionParent 를 통해 합쳐준다. 지난 포스팅에서 Union Find 알고리즘에 대해 한번 언급했으나 한번 더 언급하자면 다음과같다.

int getParent(int num){
    if(num == Parent[num]) return num;
    //입력 받은 노드와 Parent 값이 일치한다면 어차피 parent가 자신이니 그대로 return
    return Parent[num] = getParent(Parent[num]);
    //아니면 계속 타고 올라가면서 진짜 본인의 Parent를 return
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a != b) Parent[a] = b;
    //입력 받은 A, B의 Parent값이 다르다면 A의 Parent를 B의 Parent로 변경
}

bool findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    else return false;
    //A와 B의 Parent가 같으면 True, 아니면 False
}

이 세가지 함수를 활용하는 것이다. 코딩 테스트 등에서 활용하려면 이 함수들을 외우다시피 해야 할 것이다. 코드 설명은 주석에 달아두었으니 따로 하지 않겠다.

for(int i = 0; i < M; i++){
    int cost = vec[i].first;
    int src = vec[i].second.first;
    int dst = vec[i].second.second;
    if(!findParent(src, dst)){
        result += cost;
        unionParent(src, dst);
    }
}

간단하다. 아까 입력했던 간선들을 모두 뒤져가며 source Node, destination Node, 비용을 확인한 후, source와 destination 사이에 parent 가 없다면 cost를 지불하고 둘을 합친다.

왜 이게 최소한의 비용을 가져올 수 있을까? 연결을 하다보면 같은 Parent를 공유하는 노드가 나오기 마련이다. 그리고 애초에 입력받은 간선들을 가중치 기준으로 정렬했다. 즉 위의 for문에서 꺼내는 데이터들은 가중치가 적은 순서대로 정렬되어있고 우선적으로 Parent를 연결했다는 소리다.

즉 연결하다보면 어차피 Parent를 공유하는 놈이 나올테니 가중치가 적은 순으로 연결하다보면 최소 비용으로 모든 컴퓨터를 연결 시킬 수 있다는 것.

이번 포스팅에서는 Kruskal Algorithm 을 활용할 수 있는 예시를 알아보았다. 다음 포스팅에서는 똑같은 문제를 Prim Algorithm으로 풀어보도록 하겠다.