[BOJ/백준] 1922 네트워크 연결

import sys
import heapq

input = sys.stdin.readline

N = int(input())
M = int(input())
graph = [{} for i in range(N)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if a != b:
        graph[a-1][b-1] = c
        graph[b-1][a-1] = c

INF = float('inf')
distance = [INF]*N
visited = [False] *N
distance[0] = 0
node_list = []
heapq.heappush(node_list,(0,0))
result = 0
while node_list:
    dis, node = heapq.heappop(node_list)
    if visited[node]:
        continue
    result += dis
    visited[node] = True
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            distance[next_node] = graph[node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))

print(result)

최소 스패닝 트리 문제이다. 프림알고리즘과 크루스칼 알고리즘이 있는데, 크루스칼 알고리즘에 아직 익숙하지 않아, 프림 알고리즘으로 구현했다.

 

heapq를 이용해서 구현했기 때문에, distance가 갱신될때에만 heapq.heappush를 해주는 것만 주의해주면 풀 수 있는 문제이다.