[파이썬] 백준 2211 : 네트워크 복구 (골드2)

[파이썬] 백준 2211 : 네트워크 복구 (골드2)

• https://www.acmicpc.net/problem/2211

 

---

풀이

방향성 생각

• 루트 노드 1이랑 모든 노드가 연결되야 한다.
• 다른 노드까지 비용은 최소로 -> 다익
• 다른 노드와 연결될 때, 어떤 노드에서 왔는지 trace에 기록해준다.

 

---

전체코드

import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()
INF = sys.maxsize

N,M = map(int,input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,cost = map(int,input().split())
    G[a].append((b,cost)) 
    G[b].append((a,cost)) 

V = [INF]*(N+1)
V[1] = 0
trace = [None]*(N+1)
trace[1] = -1

heap = [(0,1)]
while heap:
    t,x = hq.heappop(heap)

    if V[x] < t:
        continue

    for nx,cost in G[x]:
        nt = t+cost
        if nt < V[nx]:
            V[nx] = nt
            trace[nx] = x
            hq.heappush(heap,(nt,nx))

print(N-1)
for i in range(2,N+1):
    print(i,trace[i])

---

코멘트

• node 1에서 다익을 돌려서 얻은 경로랑, MST를 돌려서 만들어진 트리랑은 다르다.