백준 1446: 지름길 - 최단경로(파이썬)

지름길 성공

1446번: 지름길

 

문제

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

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

입력

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

출력

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

 

내 코드

import sys
n,d=map(int, sys.stdin.readline().split())

#도착지가 최종목적지(d)보다 작거나 같아야 하고, 출발~도착이 지름길보다 큰놈들만 road에 저장.
road=[]
for _ in range(n):
    start, end, shortCut=map(int, sys.stdin.readline().split())
    if end<=d and (end-start)>shortCut:
        road.append([start, end ,shortCut])


#0~d까지 가는 거리를 거리별로 save에 저장할 것임.(인덱스 편하게 d+1개 생성)
save=[i for i in range(d+1)] #어떠한 지름길도 안 갔을 때로 세팅.(=위치가 곧 거리)

for i in range(d+1): 
    save[i]=min(save[i], save[i-1]+1) #현재 탐색놈을 체크후 최소값으로 최신화!
    for start, end, shotCut in road:
        if i==start: #특정 도로의 start값과 현재 위치가 같으면 지름길을 사용하자.
            save[end]=min(save[end],save[i]+shortCut) #end까지의 최소값은 min(이미 들어있는 값, 현재위치에서 지름길 쓰기)

#d까지 오는데의 최소값이 담겨있다.
print(save[d])

 

풀이 및 접근)

- 이런 최단경로 문제는, 특정 점까지 오는데까지의 최소거리를 업데이트 하면서 다음 점들에 가는 최소값을 저장하며 푸는 것이다.

- 그렇게하면 어느점에서 가는 것이 최소인지 자명하여 간단하게 구할 수 있다.