Programmers : 섬 연결하기

문제링크

풀이 요약

MST

풀이 상세

1. 문제의 “n개의 섬 사이의 다리를 건설하는 비용” 은 모든
   노드를 지날때의 최소 간선 비용을 구하는 MST 문제이다.

2. 우선순위 큐를 활용한 prim 알고리즘을 활용하자. pq 에서 간선비용이 적은 순으로 노드를 반환하도록 한다. 만약 반환된 노드가 현재 방문하지 않은 노드라면 다음 3가지 과정을 반복한다.

   • 다시 노드가 반환되지 않도록 방문처리를 한다.
   • 현재 몇개의 노드를 지나쳤는지를 확인하도록 cnt 값을 +1 한다. 모든 노드를 지나게 되었을 때, 즉 $cnt == n$ 이 되었을 때 반복과정을 종료한다.
   • $ans$ 값에 현재 노드로 이동하는데 든 비용을 더한다.

#include <vector>
#include <queue>
#define f first
#define s second
using namespace std;
vector<pair<int,int>> v[104];
int visited[104];
void input(int n, vector<vector<int>> costs) {
    for(int i=0; i<costs.size(); i++) {
        int st = costs[i][0];
        int ed = costs[i][1];
        int dist = costs[i][2];
        v[st].push_back({dist,ed});
        v[ed].push_back({dist,st});
    }
}

int solve(int n) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; 
    pq.push({0,0});
    int ans = 0;
    int cnt = 0;
    while(cnt != n) {
        pair<int,int> curr = pq.top();
        pq.pop();
        if(!visited[curr.s]) {
           ans += curr.f;
           visited[curr.s]++;
           for(auto next : v[curr.s]) pq.push(next);
           cnt++;
        }
    }
    
    return ans;
}

int solution(int n, vector<vector<int>> costs) {
    input(n, costs);
    return solve(n);
}