[백준][Python] 2211 네트워크복구

처음엔 네크워킹만 보고 MST생각해서 바로 크루스칼로 풀었는데 틀렸다.

"복구 전보다 모든 컴퓨터에 대해 전송시간이 짧아야한다"

이걸 맵 전체로 해석했기 때문인데 사실은 모든 노드에 대해 최소 거리를 가져야 한다는 말이다.

import sys
input = sys.stdin.readline

def find(x):
    if parents[x]==x:
        return x
    parents[x] = find(parents[x])
    return parents[x]

def union(a,b):
    a = find(a)
    b = find(b)

    if a>b:
        parents[a] = b
    else:
        parents[b] = a

# N개의 컴퓨터 네트워크.
# 회선은 성능차이가 있음.
N,M = map(int,input().split())
sercuits = []
parents = [i for i in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    sercuits.append([C,A,B])

sercuits.sort(reverse=True)

cnt=0
restore_line=[]
while sercuits:
    time,a,b = sercuits.pop()

    if find(a) != find(b):
        union(a,b)
        cnt+=1
        restore_line.append([a,b])

print(cnt)
for line in restore_line:
    print(*line)

때문에 다익스트라로 다시풀었다. 모든 노드에 대해 이어져있고 path 딕셔너리에 마지막으로 최신화된 이동의 경로까지 기록해줬다.

import sys
input = sys.stdin.readline
from heapq import heappop,heappush

def dijkstra(start):
    heap = []
    dp_dists[start] = 0
    heappush(heap,[dp_dists[start],start])
    while heap:
        cur_dists,cur_node= heappop(heap)
        for next_dists,next_node in network[cur_node]:
            if dp_dists[next_node] > cur_dists + next_dists:
                dp_dists[next_node] = cur_dists + next_dists
                path[next_node] = cur_node
                heap.append([dp_dists[next_node],next_node])

N,M = map(int,input().split())
network = {i:[] for i in range(1,N+1)}
dp_dists = {i:float('inf') for i in range(1,N+1)}
path = {i:0 for i in range(1,N+1)}
for _ in range(M):
    A,B,C = map(int,input().split())
    network[A].append([C,B])
    network[B].append([C,A])

dijkstra(1)

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