[실버 1] 백준 1446 - 지름길 (파이썬)

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

풀이

• 일반 도로는 i → i+1로 이동하면서 1km가 걸린다.
• 지름길은 입력으로 주어지며 (a, b, c)의 의미는 a → b로 가는 지름길이 있고, 길이는 c이다.
• 목표는 0 → D까지 가는 데 걸리는 최단 거리를 구하는 것.

N, D = map(int, input().split())
adj = [[] for _ in range(D + 1)]

D까지의 거리이므로 정점은 0부터 D까지 총 D + 1개이다.

adj[i]는 정점 i에서 갈 수 있는 목적지, 비용 리스트이다.

for _ in range(N):
    a, b, c = map(int, input().split())
    if b <= D:
        adj[a].append((b, c))

지름길 정보는 b가 D보다 큰 경우 무의미하므로 무시하며, 지름길은 단방향 간선으로 추가한다.

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

일반 도로를 연결하며 i → i + 1 거리를 모두 1로 연결한다.

dist = [1e9] * (D + 1)
pq = PriorityQueue()
pq.put((0, 0))
dist[0] = 0

다익스트라 알고리즘을 작성하며, 거리 배열 초기화 후 시작점 0에서 다익스트라를 시작한다.

while pq.qsize() != 0:
    d, u = pq.get()

    if d != dist[u]:
        continue

    for v, w in adj[u]:
        if dist[v] > dist[u] + w:
            dist[v] = dist[u] + w
            pq.put((dist[v], v))

PriorityQueue를 사용한 다익스트라 기본 틀이며, dist[u]가 지금 꺼낸 d랑 다르면 이전에 더 짧은 경로가 이미 처리되었으므로 지나간다.

코드

# 백준 1446 - 지름길
# 분류 : 다익스트라

from queue import PriorityQueue

N, D = map(int, input().split())
adj = [[] for _ in range(D + 1)]

for _ in range(N) :
    a, b, c = map(int, input().split())
    if b <= D :
        adj[a].append((b, c))

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

dist = [1e9] * (D + 1)
pq = PriorityQueue()
pq.put((0, 0))
dist[0] = 0

while pq.qsize() != 0 :
    d, u = pq.get()

    if d != dist[u] :
        continue

    for v, w in adj[u] :
        if dist[v] > dist[u] + w :
            dist[v] = dist[u] + w
            pq.put((dist[v], v))

print(dist[D])