[프로그래머스 Lv3] : 섬 연결하기

문제 링크

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

코딩테스트 연습 - 섬 연결하기

최소비용으로 n개의 섬이 모두 연결될 수 있도록 하는 문제.

 

풀이

다리를 통해서 통행이 가능하다면 두 섬은 연결되어있다고 본다.

문제를 보면 최소스패닝 트리 문제인 것을 알 수 있다.

최소 스패닝 트리를 이용해서 모든 섬이 공통 조상을 가지도록 연결시켜주면 된다.

 

코드 작성

#include <string>
#include <vector>
#include <queue>
using namespace std;
const int MAX_N = 100 + 5;
int Parent[MAX_N];
 
int Find(int x){
    if(Parent[x] == x)
        return x;
    return Parent[x] = Find(Parent[x]);
} 
 
void Union(int x, int y){
    int parent_x = Find(x);
    int parent_y = Find(y);
    Parent[parent_y] = parent_x;
}
 
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    for(int i = 0; i<n ;i++)
        Parent[i] = i;
    priority_queue<pair<int,pair<int,int>>> pq;
    
    for(int i = 0; i<costs.size(); i++)
        pq.push({-costs[i][2],{costs[i][0], costs[i][1]}});
    
    while(!pq.empty()){
        int cost = -pq.top().first;
        int u = pq.top().second.first;
        int v = pq.top().second.second;
        pq.pop();
        if(Find(u) != Find(v)){ //서로 연결되어있지 않으면
            Union(u,v);
            answer += cost;
        }
        else continue;
    }
    return answer;
}