[Python] 백준 / silver / 1446 : 지름길

문제 링크 : https://www.acmicpc.net/problem/1446

최단거리 문제고, 다익스트라 알고리즘을 적용해서 풀 수 있었다. 다익스트라 알고리즘은 외우고 있어서 괜찮은데 다익스트라를 어떻게 적용해야 할지 판단하는 것이 관건이었던 것 같다.

다익스트라는 기본적으로 그래프 구조에서 사용하는 알고리즘이기 때문에 노드와 간선이 필요하다. 그런데 이 문제에선 명확하게 노드가 뭔지 판단하기 애매했다. 시작 노드를 0, 도착 노드를 문제에서 준 D 로 설정하고, 1,2,3,4,...,D-1,D 를 모두 노드로 간주하는거다. Python heapq 를 활용한 다익스트라 알고리즘은 O(E logV) 이고, 이 문제에서 D는 최대 10,000 이기 때문에 그래도 된다.

파이썬 코드

import sys
import heapq
N, D = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(D+1)]

for i in range(D):
    graph[i].append((i+1, 1))

for i in range(N):
    start, end, length = map(int, sys.stdin.readline().split())
    if end > D: continue
    graph[start].append((end, length))

INF = 987654321
distance = [INF]*(D+1)
distance[0] = 0

q = []
heapq.heappush(q, (0, 0))
while q:
    d, now = heapq.heappop(q)
    if distance[now] < d: continue

    for x in graph[now]:
        cost = d + x[1]

        if distance[x[0]] > cost:
            distance[x[0]] = cost
            heapq.heappush(q, (cost, x[0]))

print(distance[D])