다익스트라 - 2211번: 네트워크 복구

MST (Minimum Spanning Tree)

• 모든 노드를 연결하되, 간선 가중치 합이 최소가 되도록 만드는 트리
• 출발 노드라는 개념이 없음
  ex) 전체 네트워크 구축 비용을 최소화하고 싶을 때
  -> MST의 경로는 “최단 경로”를 보장하지 않음!

SPT (Shortest Path Tree)

• 특정 시작점(여기서는 1번)에서 모든 노드까지의 최단경로만 모은 트리
• 다익스트라 + prev 배열로 구하기
  ex) 특정 시작점에서 모든 노드까지 최단경로를 보장하고 싶을 때

- 문제 요구사항: “1번에서 다른 노드까지 최단 통신망 복구”

from collections import defaultdict
import heapq, sys

input = sys.stdin.readline
# 최소 개수 회선 복구
# 슈퍼 컴퓨터가 다른 컴퓨터와 통신하는 데 걸리는 최소 시간 < 원래의 네트워크에서 통신하는데 걸리는 최소 시간

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

graph = defaultdict(list)


for i in range(m):
    line = list(map(int, input().split()))
    a, b, c = line[0], line[1], line[2]

    graph[a].append((b, c))
    graph[b].append((a, c))


def dijkstra(graph, start, n):

    hp = []
    dist = [float("inf")] * (n + 1)
    dist[start] = 0  # 시작점 0으로 꼭 초기화!!!!
    prev = [-1] * (n + 1)
    heapq.heappush(hp, (0, start))

    while hp:
        cost, node = heapq.heappop(hp)

        if dist[node] < cost:
            continue

        child = graph[node]

        for next, weight in child:  # 다음 노드, 비용 순 저장 주의!
            new_cost = weight + cost
            if dist[next] > new_cost:
                dist[next] = new_cost
                prev[next] = node
                heapq.heappush(hp, (new_cost, next))

    return dist, prev


# def get_path(prev, end):
#     curr = end
#     path = []
#     while curr != -1:
#         path.append(curr)
#         curr = prev[curr]

#     return path[::-1]


dist, prev = dijkstra(graph, 1, n)
# all_path = set()

# for i in range(2, n + 1):
#     path = get_path(prev, i)
#     # print(path)
#     for j in range(len(path) - 1):
#         p = (path[j], path[j + 1])

#         all_path.add(p)


print(n - 1)  # 항상 SPT의 전체 엣지 수는 n - 1개
for i in range(2, n + 1):
    print(i, prev[i])


# print(len(all_path))

# while all_path:
#     a, b = all_path.pop()

#     print(a, b)