[백준 1446번] 파이썬 - 지름길

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

1446번: 지름길

 

 

# 조건

- D km 길이의 고속도로를 지나는데 이 고속도로는 심각하게 커브가 많아 운전하기 힘들다.
- 이 고속도로에는 지름길이 존재하는데
- 모든 지름길은 일방통행이며, 고속도로 역주행은 불가
- 운전해야하는 최소 거리를 구하여라

 

# 접근 방법 및 풀이 과정

- 문제를 읽으며 드는 생각은 거리를 기록해둔 후 이를 통하여 최소 값을 구하면 될 것같다.
- 내가 이용하는 지름길의 거리와, 이를 이용하지 않고 고속도로를 탔을 때의 거리를 비교하는 방법!
- 지름길을 반복해주는 이유 
       - 이전 지름길의 값이 적용이 안되어있기 때문에
       - 즉, 앞에서 값이 바뀌면 뒤의 지름길을 사용한 누적거리도 변하여야 되는데, 반복을 해주지 않는다면
       - 누적거리가 적용이 안되기 때문

 

 

import sys  
input = sys.stdin.readline  
# 지름길 수 N, 고속도로 길이 D  
N, D = map(int, input().split())  
  
# 전체 길이 리스트 -> 0부터 시작하므로 +1  
highway = [i for i in range(D+1)]  
  
shortcut = [list(map(int, input().split())) for _ in range(N)]  
  
# 입력받은 지름길 시작, 도착, 길이를 받아주었으니  
# 고속도로 달리면서 지름길을 탓을 때의 이동거리를 기록해준다.  
for i in range(D+1):  
    # 출발한 이후라면  
    if not i == 0:  
        # 현재 기록되어있는 이동거리 vs 1km 이전에 기록되어있는 거리 +1 중 작은 것  
        highway[i] = min(highway[i], highway[i-1]+1)  
    for start, end, length in shortcut:  
        # 도착점이 전체길이를 넘지 않고, 이동거리가 최소값이라면 = 출발지점까지 이동거리 + 지름길 길이.  
        if end <= D and highway[start]+length < highway[end]:  
            # 지름길 도착지점까지 이동거리 변겅  
            highway[end] = highway[start] + length  
  
  
print(highway[-1])

 

• 다익스트라 문제이지만 heapq를 사용하지 않고 풀 수 있는 문제였다.
• 다익스트라 알고리즘에 대해서는 게시물 업로드 후 링크 달기@