[백준]2211 네트워크복구 #다익스트라#mst

1. 풀이 

아래와 같은 2번조건이

네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

위와같이 충족되어야 하기 때문에, 다익스트라를 이용하여 그래프를 만들어 나간다.

다익스트라에서 노드들의 거리를 업데이트 할 때, 특정노드의 이전노드도 같이 업데이트 해주며 edge들을 파악해 준다.

다익스트라를 이용해서 mst를 만드는건 어렵지 않은데, 위의 알고리즘을 적용하기 위해선, "다익스트라를 이용해 이은 간선들이 항상 MST를 만든다" 라는 전제조건이 있어야 한다.

(1) 이는 1번노드(1번 컴퓨터)에서 모든 노드까지의 거리를 구하기 때문에 반드시 연결된 그래프가 만들어 지고,  (2) 노드1 에서 N-1개의 노드들 까지의 최단거리를 구하므로 간선들도 자연히 N-1개가 찾아지기 때문에 다익스트라로 만든 그래프는 반드시 MST가 된다고 보장할 수 있다.

2. 소스코드

import heapq

inf=9876543210

N,M=map(int,input().split())
graph={}
for i in range(1,N+1):
    graph[i]=[]

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

# nodeDist[i]=[a,b] => a: 1에서 i노드까지의 거리, b: i노드의 이전노드
nodeDist=[[inf,i] for i in range(N+1)]
dij=[[0,1]]
nodeDist[1][0]=0

ans=[]

while(dij):
    cost,nowNode=heapq.heappop(dij)
    if cost>nodeDist[nowNode][0]:
        continue
    ans.append([nowNode,nodeDist[nowNode][1]])
    for toNode,toCost in graph[nowNode]:
        addedCost=cost+toCost
        if addedCost<nodeDist[toNode][0]:
            nodeDist[toNode][0]=addedCost
            nodeDist[toNode][1]=nowNode
            heapq.heappush(dij,[addedCost,toNode])

print(N-1)
for i in range(1,N):
    print(*ans[i])