[최단 경로] 백준 1753번: 최단 경로

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

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.

www.acmicpc.net

import collections
import heapq
n, m = map(int, input().split())
k = int(input())

# construct graph
graph = collections.defaultdict(list)
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append([v,w])

dist = {}
def dijkstra(node):
    q = [[0, node]] # time, departure
    while q:
        time, cur = heapq.heappop(q)
        if cur not in dist:
            dist[cur] = time
            for next, w in graph[cur]:
                heapq.heappush(q, [w + time, next])

dijkstra(k)

for i in range(1, n+1):
    if i in dist.keys():
        print(dist[i])
    else:
        print('INF')

배운점

- 다익스트라는 BFS와 우선순위큐를 사용하여 구현한다.

- 위의 기본틀을 기억하자. while.. if.. for..

- q안의 항목들을 시간이 짧은 것부터 계속 꺼내가면서 그 노드와 인접한 노드를 탐색하는 방식