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

 

https://programmers.co.kr/learn/courses/30/lessons/42861?language=cpp 

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

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<pair<int, int>> v[100];
bool visited[100];

struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
	    return a.second > b.second; // 작은 값 우선
    }
};

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    for(int i=0; i<costs.size(); i++) {
        v[costs[i][0]].push_back({costs[i][1], costs[i][2]});
        v[costs[i][1]].push_back({costs[i][0], costs[i][2]});
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
    
    // 시작 정점 큐에 넣기
    for(int i=0; i<v[0].size(); i++) {
        pq.push({v[0][i].first, v[0][i].second});
    }
    visited[0] = true;
    
    while(!pq.empty()){
        int node = pq.top().first;
        int cost = pq.top().second;
        pq.pop();
        
        if (!visited[node]) {
            visited[node]=true;
            answer += cost;
            
            for(int i=0; i<v[node].size(); i++) {
                if (!visited[v[node][i].first])
                    pq.push({v[node][i].first, v[node][i].second});
            }
        }
    }
    
    return answer;
}