백준 2211 : 네트워크 복구 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline
INF=int(1e9)

def Dijkstra():

    dp[1]=0
    heap=[] ; heapq.heappush(heap , (0,1))

    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

        for next_value,next_node in graph[node]:

            next_value+=value

            if next_value<dp[next_node]:
                dp[next_node]=next_value
                check[next_node]=node
                heapq.heappush(heap, (next_value , next_node))


N,M=map(int,input().split())

graph=[ [] for _ in range(N+1) ]
dp=[INF]*(N+1)
check=[0]*(N+1)

ALL=[]
for i in range(M):
    A,B,C=map(int,input().split())
    graph[A].append((C,B))
    graph[B].append((C,A))

    ALL.append((A , B))

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

📌 아떻게 접근할 것인가?

다익스트라를 통해 풀었습니다.

모든 정점을 연결해야 하므로 연결해야하는 간선의 개수는 항상 $N-1$ 개 입니다.
또한 역추적을 하기 위해서 check[next_node]=node 와 같이 다음노드에 이전노드의 값을 저장해서

반복문을 통해 역추적한 결과를 출력해줍니다. 순서는 상관없습니다.