문제 링크

풀이 과정

• 문제의 목표는 최소의 비용으로 모든 섬이 서로 통행 가능하도록 하는 것입니다.
  • 즉, 최소한으로 다리를 설치하여 섬을 이어줘야 합니다.
  • 결과적으로, 최소 신장 트리 를 구현하는 문제임을 파악할 수 있습니다.
• 본 풀이에서는, 프림 알고리즘을 이용하여 최소 신장 트리를 구현하도록 하겠습니다.

<Solution>
그래프를 초기화한다(각 정점 별 이웃 정점 및 가중치 저장)
0번 노드를 출발 지점으로 한다.
cost 배열을 초기화한다. (이웃 정점에서 출발하여, 해당 정점에 도착하기 위해 필요한 최소 비용)
노드 set을 초기화한다. (사이클 형성 여부 확인)
최소 힙을 초기화한다. (비용, 정점)

노드 set에 모든 정점이 포함될 때까지 다음 동작을 반복한다:
		최소 힙에서 현재 비용, 현재 노드를 추출한다.
		만약 현재 노드가 사이클을 형성한다면:   continue
		그렇지 않다면:
		    노드 set에 현재 정점을 추가한다.
		    현재 정점에 대한 cost 배열 값을 갱신한다.
		    현재 정점과 이웃한 모든 정점을 최소 힙에 추가한다.

전체 코드

import heapq
from collections import defaultdict 

def solution(n, costs):
    graph = defaultdict(dict)
    for u, v, cost in costs:
        graph[u][v] = cost
        graph[v][u] = cost
    
    costs = [0 for _ in range(n)]
    node_set = {0}   # 0번 노드에서 출발
    
    heap = []
    for node, cost in graph[0].items():
        heapq.heappush(heap, (cost, node))
    
    while len(node_set) < n:
        cur_cost, cur_node = heapq.heappop(heap)
        if cur_node in node_set:    continue
        
        node_set.add(cur_node)
        costs[cur_node] = cur_cost
        
        for neighbor, cost in graph[cur_node].items():
            heapq.heappush(heap, (cost, neighbor))            
           
    return sum(costs)