BOJ - 2211

백준 문제 링크
네트워크 복구

❓접근법

1. 다익스트라 알고리즘을 활용했다.
2. 기본 다익스트라 소스코드에
   parent = [0] * (N + 1)을 가지는 리스트를 하나 만들어준다.
   parent는 최종적으로 연결해야하는 노드의 번호를 저장하기 위함.
3. 다익스트라 소스코드를 전개하고, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이므로 노드 번호를 1부터 시작한다.
4. 모든 정점을 연결해야하므로 간선의 개수는 항상 N - 1개,
   복구한 회선은 i를 2부터 n + 1까지 증가시켜
   i, parent[i]로 출력하면 된다.

👌🏻코드

import heapq

INF = int(1e9)

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

graph = [[] for _ in range(n + 1)]

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

distance = [INF] * (n + 1)
parent = [0] * (n + 1)

def dijkstra(start):
    
    
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        
        if distance[now] < dist:
            continue
            
        for i in graph[now]:
            cost = dist + i[1]
            
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                parent[i[0]] = now
                
dijkstra(1)

print(n - 1)
for i in range(2, n + 1):
    print(i, parent[i])