[Python] 2211.네트워크 복구

문제

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

2211번: 네트워크 복구

---

풀이과정

컴퓨터와 시간을 주고 최소 시간으로 모든 컴퓨터를 연결해야 한다. 그리고 연결하는 횟수와 연결할 컴퓨터의 번호를 출력하는 문제이다.
따라서 노드와 거리(시간)이 있고 최단 거리 찾기라고 생각하여 다익스트라 알고리즘을 활용하여 풀었다.  

처음에는 for문으로 dijkstra 함수를 모든 컴퓨터에서 시작시켜서 거기서 가장 시간이 적게 드는 곳을 연결해야지 라고 생각해서 컴퓨터마다 dijkstra 함수를 실행시킨 후, 제일 적은 시간이 걸린 컴퓨터 체크와 중복 체크 등 지저분한 코드를 짰다. 당연히 시간 초과가 났고 dijkstra 함수 안에서 연결할 컴퓨터를 갱신하라는 힌트를 얻어 풀게 되었다.

---

코드

import heapq

def dijkstra(s):
    dist = [float('inf') for _ in range(n+1)]
    queue = []
    heapq.heappush(queue, [0, s])
    dist[s] = 0
    while queue:
        d, now = heapq.heappop(queue)

        if dist[now] < d:
            continue

        for nxt, nxt_d in network[now]:
            new_d = nxt_d + d
            if new_d < dist[nxt]:
                # 모든 컴퓨터에서 최단 거리를 찾아야 한다.
                # 해당 컴퓨터에서 더 짧은 거리가 있으면 connecting_info(이어질 컴퓨터) 갱신
                connecting_info[nxt] = now
                dist[nxt] = new_d
                heapq.heappush(queue, [new_d, nxt])


n, m = map(int, input().split())

network = [[] for _ in range(n+1)]
for _ in range(m):
    com1, com2, time = map(int, input().split())
    network[com1].append([com2, time])
    network[com2].append([com1, time])

connecting_info = [0 for _ in range(n+1)]
dijkstra(1)

print(n-1)  # 모든 컴퓨터가 이어져야 하는 것이니 n-1
for i in range(2, n+1):
    print(i, connecting_info[i])