[프로그래머스] 섬 연결하기 / Minimum Spanning Tree, Kruskal MST, Union-find / C++ 풀이

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

 

풀이 전략

n개의 섬을 최소한의 비용으로 전부 연결해야 한다. 최소 신장 트리(Minimum spanning tree)는 그래프의 정점들을 최소의 비용으로 전부 연결한다. 이 때, n개의 정점에 대해 (n-1)개의 간선을 사용하여 연결한다. 

 

Kruskal MST 알고리즘

비용이 가장 적은 간선부터 n개의 정점을 전부 연결 할 때까지 선택해 나간다. 서로 연결된 정점들은 하나의 '그룹'이라고 표현한다면 모든 정점들이 하나의 그룹에 속할 때 까지 간선을 연결하면 된다. 이 과정에서 Union-Find를 사용한다. 어떤 간선이 이미 같은 그룹에 속한 두 정점을 연결하는 것이라면 이 간선은 MST에 포함시키지 않는다. 만약 서로 다른 그룹을 연결한다면 MST에 포함시킨다.

 

C++ 풀이

/*
https://school.programmers.co.kr/learn/courses/30/lessons/42861
*/
#include <vector>
#include <queue>
using namespace std;

vector<int> parent; /*group*/

/*Union-find*/
int getParent(const int island) {
    if(parent[island] == island) {
        return island;
    }
    else {
        return parent[island] = getParent(parent[island]);
    }
}

int solution(int n, vector<vector<int>> costs) {
    parent.resize(n);
    for(int i = 0; i < n; ++i) {
        parent[i] = i;
    }
    
    priority_queue<vector<int>, vector<vector<int>>, greater<>> pq;
    for(const auto& c : costs) {
        pq.push({c[2],c[0],c[1]});
    }
    
    int answer = 0;
    int bridgeCnt = 0;
    
    while(true) {
        int a = pq.top()[1];
        int b = pq.top()[2];
        
        int ap = getParent(a);
        int bp = getParent(b);
        
        if(ap != bp) {
            answer += pq.top()[0];
            parent[ap] = bp;
            if(++bridgeCnt == n-1) {
                break;
            }
        }
        
        pq.pop();
    }
    
    return answer;
}