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

- 문제설명

 

- 풀이코드

#include <string>
#include <queue>
#include <vector>
#include <iostream>
 
//https://programmers.co.kr/learn/courses/30/lessons/42861
 
using namespace std;
 
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    vector<vector<pair<int,int>>> graph (n);
    for(auto cost : costs){
        int from = cost[0];
        int to = cost[1];
        int weight = cost[2];
        graph[from].push_back(make_pair(to,weight));
        graph[to].push_back(make_pair(from,weight));
    }
    
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> p_q;
    vector<int> visited(n,0);
    p_q.push(make_pair(0,1));
    while(!p_q.empty()){
        int cost = p_q.top().first;
        int v = p_q.top().second;
        p_q.pop();
        if(visited[v]==1) continue;
        answer += cost;
        visited[v] = 1;
        for(int i=0;i<graph[v].size();i++){
            int to = graph[v][i].first;
            int weight = graph[v][i].second;
            if(visited[to]==0){
                p_q.push(make_pair(weight,to));
            }
        }
    }       
    return answer;
}

 

- 시간복잡도

시간 복잡도 O(nlogn)

n(노드의 수) * logn(힙연산)

 

- 남의 풀이와 비교

MST 문제로서 크루스칼 알고리즘, 프림 알고리즘 두가지 방법이 있는데 나는 힙을 사용하여 프림 방법으로 풀었다.

처음에 아무 생각없이 다익스트라로 접근했었는데 다익스트라의 경우에는 시작점에 따라 최소비용이 달라지기 때문에 이문제에 적합하지 않다.

 

- Reference

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