[프로그래머스] [C++] 섬 연결하기 (prim)

1. 문제

코딩테스트 연습 - 섬 연결하기 | 프로그래머스 (programmers.co.kr)

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

 

2. Prim 알고리즘

 

 prim 알고리즘은 그리디적으로 mst를 찾는 알고리즘이다.

 

따라서 이 문제에서 주어지는 입력을 인접 그래프 형태로 나타내고

 

우선순위 큐를 활용한 프림 알고리즘을 사용하면 문제는 해결된다.

 

프림 알고리즘말고도 크루스칼 알고리즘을 사용할 수 있으며, 이때 따로 정렬과, 

 

유니온 파인드 자료구조를 사용해야한다,

 

하지만 이 경우 따로 그래프를 재구성할 필요가 없다.

#include <string>
#include <vector>
#include <queue>
#include <numeric>
 
using namespace std;
 
const int MAXI = 1234567890;
 
vector<vector<int>> make_graph(int n, vector<vector<int>> costs) {
    vector<vector<int>> adj(n, vector<int>(n, 0));
    for(int i = 0; i < costs.size(); i++) {
        adj[costs[i][0]][costs[i][1]] = costs[i][2];
        adj[costs[i][1]][costs[i][0]] = costs[i][2];
    }
    return adj;
}
 
int prim(int src, int n, const vector<vector<int>>& adj) {
    vector<int> minDist(n, MAXI);
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, src));
 
    while(!pq.empty()) {
        int here = pq.top().second;
        int dist = -pq.top().first;
        pq.pop();
        if(minDist[here] <= dist)
            continue;
        minDist[here] = dist;
        for(int there = 0; there < n; there++) {
            if(adj[here][there] && minDist[there] == MAXI) {
                pq.push(make_pair(-adj[here][there], there));
            }
        }
    }
    return accumulate(minDist.begin(), minDist.end(), 0);
}
 
int solution(int n, vector<vector<int>> costs) {
    return prim(0, n, make_graph(n, costs));
}