[백준/1446] 지름길 (Python)

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

1446번: 지름길

 

Difficulty : Silver 1

 

Status : Solved

 

Time : 00:20:12

 

---

 

문제 설명

 

 

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

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

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

 

출력 예시

 

70

 

 

---

 

풀이

 

제약조건이 많고, 최대 지름길 개수 N이 12 이하이므로 다양한 방법을 시도해 볼 수 있겠다. 빡세게 O(ElogV)의 다익스트라 알고리즘을 고려해볼 수도 있고, 단순 경로탐색 문제로 가정하고 풀이해볼 수 있다. 혹은 도착점을 기준으로 DP를 적용시켜볼 수도 있을 것이다.

 

여기서 생각해보아야 할 점 두 가지만 고려해보자.

• 지름길을 이용하지 않는 경우를 생각해야 한다. 즉 지금 시점에서 고속도로 출구까지 어느 지점에서든 바로 이동할 수 있으므로, 경로 최솟값은 이 점을 염두해두고 계산되어야 한다.
• 지름길이 일반도로보다 소모비용이 크거나, 지름길을 사용했을 때 출구를 지나치는 경우가 있다. 전자는 더 비효율적이며, 후자는 정답이 될 수 없다. (역주행이 불가능하다)

 

풀이 코드

from collections import deque, defaultdict
import sys

input = sys.stdin.readline
N, D = map(int, input().split())
map_list = [list(map(int, input().split())) for _ in range(N)]
q = deque([(0, 0)])
result = D
while q :
  node, dist = q.popleft()
  if dist + D - node < result :
    result = dist + D - node
  for start, end, cost in map_list :
    if start < node or end > D :
      continue
    q.append((end, dist + start - node + cost))
    
print(result)

풀이 완료!