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

프로그래머스의 Lv.3 섬 연결하기입니다.

문제 출처

섬 연결하기

문제 해설

문제의 핵심을 요약해보자.

1. 섬의 개수는 1개 이상 100개 이하이다.
2. 섬을 연결하는 다리가 있고, 해당 다리에는 비용이 있다.
3. 모든 섬을 서로 통행 가능하도록 다리를 만들 때, 최소비용을 구해야한다.
   

위의 요약에 따라 생각해보면, 이 문제는 최소 신장 트리 문제이다.
나는 최소 신장 트리에서도 프림 알고리즘을 사용해서 문제를 해결했다.

#include <bits/stdc++.h>

using namespace std;

bool check[101];

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    int startPoint = 0;
    
    vector<pair<int, int>> v[101];
    for(int i=0;i<costs.size();++i){
        int start = costs[i][0];
        int end = costs[i][1];
        int cost = costs[i][2];
        v[start].push_back({end, cost});
        v[end].push_back({start,cost});
        startPoint = start;
    }
    
    priority_queue<tuple<int,int,int>
                    , vector<tuple<int,int,int>>
                    , greater<tuple<int,int,int>>> pq;    
    
    check[startPoint] = true;
    for(auto cur : v[startPoint]){
        pq.push({cur.second, startPoint, cur.first});
    }
    int count = 1;
    while(count < n){
        int cost, start, end;
        tie(cost, start, end) = pq.top(); pq.pop();
        if(check[end] == true) continue;
        check[end] = true;
        answer += cost;
        ++count;
        for(auto a : v[end]){
            if(check[a.first] == false)
                pq.push({a.second, end, a.first});
        }
    }
    
    
    return answer;
}