[백준] 2211 네트워크 복구, python

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

 
처음에는 유니온 파인드로 간선들을 최소비용 순으로 정렬하고 비용이 적은 간선들을 추가해 나가면서 모든 노드들이 연결되면 최소 비용이다라고 풀었는데 틀렸다.
틀렸던 이유는 유니온파인드를 사용해서 풀었던 방식은 최소 신장트리(그래프 간선들의 합이 최소)를 구하는 크루스컬 알고리즘 이었기 때문이었다.
이 문제는 최소 경로 트리(한점에서 다른 노드들까지의 최단 경로)를 구하는 다익스트라를 사용해서 풀어야 되는 문제이다.
다익스트라 알고리즘은 파이썬의 heapq를 사용해서 구현하였다.
 

 

다익스트라 알고리즘(최단경로 알고리즘), python

다익스트라 알고리즘(최단경로 알고리즘), python

 

 

 

출발노드에서 각 노드까지의 최단 경로를 저장하는 배열 d를 생성한다.
출발 노드의 d값은 0으로, 나머지는 inf로 초기화한다.
힙에서 (현재까지의 거리, 노드번호)를 꺼낸다.
힙에서 꺼낸 거리값이 d[노드번호] 보다 크다면 이미 더 짧은 경로가 존재한다는 것이므로 건너뛴다.
현재 노드에서 연결된 노드들의 d값을 갱신해 준다.
d [현재노드] + 다음 노드까지의 거리 가 d [다음 노드]보다 작다면 기존 경로보다 더 짧은 경로가 있다는 것이므로 갱신하고 힙에 넣는다.
위 과정을 힙을 모두 비울 때까지 반복한다.
 

 
노드까지의 최단 경로를 담은 배열을 d를 생성했다. 초기값은 inf를 넣었다.

d	방문한 노드	힙	설명
[0,inf,inf,inf]		[(0,1)]	처음 시작하는 노드의 최단거리는 0이다. 시작노드(1번노드)를 힙에 넣어준다.
[0,1,2,4]	1	[(1,2),(2,3),(4,4)]	힙에서 하나를 꺼낸다. 꺼낸노드(1번노드)에서 연결된 노드는 2,3,4번이다. d[1번노드] + 1 가 d[2번노드] 보다 작으므로 갱신하고 힙에 넣는다. d[1번노드] + 2 가 d[3번노드] 보다 작으므로 갱신하고 힙에 넣는다. d[1번노드] + 4 가 d[4번노드] 보다 작으므로 갱신하고 힙에 넣는다.
[0,1,2,3]	1,2	[(2,3),(3,4),(4,4)]	힙에서 하나를 꺼낸다. 꺼낸노드(2번노드)에서 연결된 노드는 1,4번이다. d[2번노드] + 1 가 d[1번노드] 보다 크므로 갱신하지 않는다. d[2번노드] + 2 가 d[4번노드] 보다 작으므로 갱신하고 힙에 넣는다.
[0,1,2,3]	1,2,3	[(3,4),(4,4)]	힙에서 하나를 꺼낸다. 꺼낸노드(3번노드)에서 연결된 노드는 1, 4번이다. d[3번노드] + 1 가 d[1번노드] 보다 크므로 갱신하지 않는다. d[3번노드] + 3 가 d[4번노드] 보다 크므로 갱신하지 않는다.
[0,1,2,3]	1,2,3,4	[(4,4)]	힙에서 하나를 꺼낸다. 꺼낸노드(4번노드)에서 연결된 노드는 1,2,3번이다. d[4번노드] + 4 가 d[1번노드] 보다 크므로 갱신하지 않는다. d[4번노드] + 2 가 d[2번노드] 보다 크므로 갱신하지 않는다. d[4번노드] + 3 가 d[3번노드] 보다 크므로 갱신하지 않는다.
[0,1,2,3]	1,2,3,4	[]	힙에서 하나를 꺼낸다. 꺼낸노드(4번노드)의 d값은 3인데 힙에서 꺼낸 d값은 4이므로 건너뛴다.

 
 

import sys
sys.setrecursionlimit(10**6)
import heapq
input = sys.stdin.readline

n, m = list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x,y,w = list(map(int,input().split()))
    graph[x].append([y,w])
    graph[y].append([x,w])

               
cur = 1
heap = []
heapq.heappush(heap,(0,1))
dp = [float('inf')]*(n+1)
dp[1] = 0
prev = [x for x in range(n+1)] # 간선을 구하기 위해 이전노드 저장

# 다익스트라 구현
while heap:
    dist, cur = heapq.heappop(heap)

    if dist > dp[cur]:
        continue

    for next,w in graph[cur]:
        if dp[next] > dp[cur] + w:
            dp[next] = dp[cur] + w
            prev[next] = cur # 이전노드 갱신
            heapq.heappush(heap, (dp[next], next))


print(n-1)
for i in range(1,n+1):
    if i != prev[i]:
        print(i,prev[i])