[알고리즘] 섬 연결하기

포인트

• 섬을 연결을 하는 방법은 무엇인가? 모든 섬이 최소 비용으로 연결되어 있어야 한다. 
  최단거리가 아님을 인지하자 (최소 비용으로 연결된 MST 를 구하는 문제이다. )
  결국은 연결되는 cost 를 전부 더해주는 것입니다. 
• MST 를 구하는 알고리즘은 크루스칼(union, find 를 사용합니다), 프림 등이 있다. (저는 프림을 애정합니다. )
• 시간 복잡도 O(n^2) 을 가지고 있다. 
• c++ 에서는 우선 순위 큐에서 greater<> 를 통해서 만들 수 있고, python 은 heapq 모듈을 통해서 만들 수 있다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

프림 알고리즘(min_heap 을 이용하여 구현)

#include <string>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

bool visited[105];
vector<pair<int, int>> map[105];

int solution (int n, vector<vector<int>> costs) {
    int answer=0;

    for(auto ele : costs) {
        map[ele[0]].push_back ({ ele[1], ele[2] });
        map[ele[1]].push_back ({ ele[0], ele[2] });
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	
    for(auto ele : map[0]) {
       //ele[0] 도착지 ele[1] 소요 비용
        pq.push ({ ele.second, ele.first });
    }
    visited[0]=1;

    while(!pq.empty()) {
        int cost, x;
        tie (cost, x)=pq.top ();
        pq.pop ();

        if(!visited[x]) {
            visited[x]=1;
            answer+=cost;

            for(auto ele : map[x]) {
                int nx, ncost;
                tie (nx, ncost)=ele;
                if (!visited[nx]) pq.push ({ ncost, nx });
            }
        }
    }


    return answer;
}

python

# MST 를 만드는 문제 프림 알고리즘
import heapq
from collections import defaultdict


def prim(data: dict) -> int:
    ans = 0
    pq = [[0, 0]]
    visited = set()
    while pq:
        cost, x = heapq.heappop(pq)
        if x in visited:
            continue
        visited.add(x)
        ans += cost
        for cost, nx in data[x]:
            heapq.heappush(pq, [cost, nx])

    return ans


def solution(n, costs: list):
    data = defaultdict(list)
    for a, b, cost in costs:
        data[a].append([cost, b])
        data[b].append([cost, a])

    answer = prim(data)
    return answer


print(solution(4, [[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]]))