[ 백준 / G2 / Python 파이썬 ] 네트워크 복구

링크 : https://www.acmicpc.net/problem/2211

2211번: 네트워크 복구

 

코드

---

import sys
input = sys.stdin.readline

from collections import defaultdict
from heapq import heappop,heappush

n,m = map(int,input().split())
graph = defaultdict(list)

for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((c,b))
    graph[b].append((c,a))

answer = []

dist = [1e9] * (n+1)
dist[1] = 0
link = [x for x in range(n+1)]
heap = [1]
while heap:
    node = heappop(heap)
    for w, nextNode in sorted(graph[node]):
        if dist[nextNode] > w+dist[node]:
            dist[nextNode] = w+dist[node]
            link[nextNode] = node
            heappush(heap,nextNode)
print(n-1)
for i in range(2,n+1):
    print(i,link[i])

 

풀이

---

이 문제의 핵심은 1번 노드에서 모든 노드로 향하는 최단거리를 갱신할 때, 각 노드마다 직접적으로 연결된 노드가 무엇인가이다.

예를 들어, 1 -> 2 -> 4 이 경로가 4번으로 향하는 최단경로일 때 직접적으로 연결된 노드는 2번이다.

 

모든 노드로 향하는 최단거리는 다익스트라 알고리즘으로 구했다.

여기서 최단거리를 갱신할 때마다 해당 노드에 직접 연결된 노드가 무엇인지를 저장해야 한다.

if dist[nextNode] > w+dist[node]:
    dist[nextNode] = w+dist[node]
    link[nextNode] = node

현재 (1-nextNode의 거리)가 (1-node의 거리)+(node-nextNode의 거리)보다 크다면 최단거리를 갱신해준다.

이때 1->node->nextNode의 구조가 되기 때문에 link의 nextNode는 node로 바꿔준다. 

 

이런 방식으로 모두 구하고 link배열을 돌면서 순서에 상관없이 (인덱스,값)을 출력해주면 된다.