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

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

2211번: 네트워크 복구

 

처음에는 문제의 조건이 좀 어려웠었다. 하지만 결국 최소한의 비용으로 최소한의 개수로 연결해라인데

결국 다익스트라를 사용하면 된다.

 

다익스트라로 각 점마다의 최단경로를 구할 수 있다. 하지만 경로를 저장해야한다.

그래서 나는 비용과 연결된 이전 노드를 저장했다.

2번 노드에서 3번노드로 연결되어있고 비용이 1이라면

배열[3] = (2,1)

이런식으로 저장된다.

그래서 3번노드는 2번 노드와 연결되어 있다는 의미이다.

 

그래서 1을 제외한 노드에서 거꾸로 타고 들어가보면 결국 1로 도달하게 된다.

이때의 점들을 기록하여 주면 된다.

주의할점은 점들이 중복해서 나오므로 set을 이용하여 중복을 제거해주자.

 

from sys import stdin
from heapq import heappush, heappop

input = stdin.readline
INF = 9876543210
n,m = map(int, input().split())
adj_list = [[] for _ in range(n+1)]
for _ in range(m):
    a,b,c = map(int, input().split())
    adj_list[a].append((b,c))
    adj_list[b].append((a,c))

def solv():
    visited = [[INF,-1] for _ in range(n+1)]
    pq = [(0,1)]
    visited[1] = [n+1,0]
    while pq:
        cost,now = heappop(pq)

        for nxt,nxt_cost in adj_list[now]:
            if visited[nxt][0] == INF or visited[nxt][1] > cost+nxt_cost:
                visited[nxt] = [now,cost+nxt_cost]
                heappush(pq,(cost+nxt_cost,nxt))

    answer = set()
    for now in range(2,n+1):
        nxt = visited[now][0]
        while nxt != n+1:
            answer.add((now,nxt))
            now = nxt
            nxt = visited[now][0]

    print(len(answer))
    for a,b in answer:
        print(a,b)
solv()