[백준 / 그래프] 1446 : 지름길 (python)

문제 설명

 

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

예제 입력 1

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

예제 출력 1

70

예제 입력 2

2 100
10 60 40
50 90 20

예제 출력 2

80

예제 입력 3

8 900
0 10 9
20 60 45
80 190 100
50 70 15
160 180 14
140 160 14
420 901 5
450 900 0

예제 출력 3

432

 

풀이

import heapq
import sys
input = sys.stdin.readline

E, V = map(int, input().split())
A = [[] for _ in range(V + 1)] # 노드 인접 리스트
distance = [sys.maxsize] * (V + 1) # 시작점으로부터 최단 경로 거리
q = [] # (거리, 노드 번호)

for i in range(E):
    u, v, w = map(int, input().split())
    if v > V:
        continue
    A[u].append((v, w))

# 다음 노드까지의 거리 1
for i in range(V):
    A[i].append((i + 1, 1))

distance[0] = 0
heapq.heappush(q, (distance[0], 0))

while q:
    curDist, curNode = heapq.heappop(q)

    if distance[curNode] < curDist:
        continue

    for node, dist in A[curNode]:
        distance[node] = min(distance[curNode] + dist, distance[node])
        heapq.heappush(q, (distance[node], node))

print(distance[V])

 

다익스트라 알고리즘을 이용하는 문제.

 

에지 정보를 인접 리스트(A)에 저장한다.

이때, 도착 노드 v가 전체 길이 V보다 크면 append 하지 않는다.

 

먼저 힙 자료구조에 시작 노드를 넣는다.

이후 힙이 빌때까지 while문을 돌면서 최단 경로를 찾는다.

 

while문 내에서, 우선 힙에서 가장 거리가 짧은 노드를 꺼낸다. (힙에는 (거리, 노드 번호) 형태로 저장돼있음)

꺼낸 노드에 저장된 거리가 해당 노드의 최단 경로(distance)보다 큰 경우, 힙에서 다음 노드를 꺼낸다.

그렇지 않은 경우, 해당 노드의 인접 리스트에 가서 연결된 노드들의 최단 경로를 계산한다. 그리고 연결된 노드들은 heap에 넣어준다.

 

이를 반복하면 distance에 모든 노드의 (시작점 0으로 부터) 최단 경로가 저장된다.

 

우선순위 큐로 풀면 시간초과남. 힙으로 풀어야함. (우선순위 큐도 힙으로 구현된건데 왜 시간초과 나는지는 의문)