[코테] 99클럽 코테 스터디 3일차 TIL (BOJ 2211)

문제

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

풀이

다익스트라 알고리즘을 이용하여 슈퍼컴퓨터(1번 노드)를 중심으로 다른 모든 컴퓨터들과의 최소 비용 경로를 계산하고 각 컴퓨터가 통신을 위해 연결해야 할 노드(부모노드)를 parent에 저장하였다.

import heapq
import sys

INF = sys.maxsize
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
parent = [0] * (n+1)

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

def dijkstra(start):
    queue = []
    distance = [INF] * (n+1)
    distance[start] = 0
    heapq.heappush(queue, (0, start))

    while queue:
        dist, now = heapq.heappop(queue)

        if dist > distance[now]:
            continue

        for node, node_cost in graph[now]:
            cost = node_cost + dist

            if cost < distance[node]:
                distance[node] = cost
                parent[node] = now
                heapq.heappush(queue, (cost, node))

dijkstra(1)

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

TIL

이전에 공부했던 다익스트라 알고리즘을 직접 구현하며 복기하였다.