[백준] 1922 네트워크 연결 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1922
• 🔑 최소 비용 신장 트리, 프림 알고리즘
  • 양방향으로 그래프를 생성
  • 힙 (비용, 출발 노드)로 초기화, 출발 노드는 어떤 노드라도 상관없음
  • 그래프를 탐색하면서 방문 안 한 노드면 방문 처리하고 정답에 비용을 더한다.
  • 그다음 현재 노드와 연결된 노드들을 힙에 넣는다.
  • 이렇게 해서 최소 비용이 구해지는 이유는 힙으로 구현했기 때문에 현재 노드와 연결된 노드 중 최소 비용인 노드가 먼저 뽑히게 되고 이 노드는 방문처리가 되기 때문에 최소 비용이 아닌 길로는 가지 않는다.

 

import sys
from heapq import heappop, heappush
from collections import defaultdict

n = int(input())
m = int(input())

tree = defaultdict(list)

for i in range(m):
    a, b, c = map(int, input().split())
    tree[a].append((c, b))  # 비용 먼저
    tree[b].append((c, a))  # 양방향

heap = [(0, 1)]             # 비용, 노드
visit = [False] * (n+1)
answer = 0

while heap:
    cost, node = heappop(heap)

    if not visit[node]:
        visit[node] = True
        answer += cost

        for next_cost, next_node in tree[node]:
            heappush(heap, (next_cost, next_node))

print(answer)