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

[백준][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])

from http://devlibrary00108.tistory.com/152 by ccl(A) rewrite - 2021-07-30 18:00:27