https://www.acmicpc.net/problem/1446
거리가 D km 인 도로에서 지름길이 있으면 더 빠르게 이동해서 최소로 이동하게끔 하는 문제다.
다익스트라 문제는 풀어도 풀어도 어렵다. 🤯
다익스트라 배열 moved_distance 리스트를 만들어주었다.
moved_distance[i] = 거리 i 까지 이동했을 때, 최적으로 이동한 거리
더 작은 값을 비교하면서 배열에 넣어야하므로 큰 값으로 배열을 초기화 해준다.
moved_distance = [99999 for _ in range(d+1)]
그리고 0부터 한칸씩 이동하면서 각 지점에 대한 최단 거리를 처리해줬다.
지름길을 타고 도착하는 경우
vs 현재 moved_distance
값 중 더 작은 값으로 갱신해준다.moved_distance[다음 지점(;해당 지점 + 1)]
값이 현재 moved_distance + 1
보다 크면moved_distance[다음 지점]
의 값을 moved_distance[현재 지점] + 1
로 갱신해준다.그리고 moved_distance의 d번째 칸을 출력해주면, 거리 d까지 이동했을 때, 최적의 값이 출력된다.
import sys
import collections
input = sys.stdin.readline
#지름길 개수 n, 고속도로 길이 d
n, d = map(int,input().rstrip().rsplit())
graph = [[] for _ in range(n)]
moved_distance = [99999 for _ in range(d+1)]
for i in range(n):
start, end, length = map(int,input().rstrip().rsplit())
graph[i]=(start,end,length)
graph.sort()
# 입력이 랜덤으로 오름차순으로 안들어올 수도 있으니
# 그래프의 값을 오름차순으로 정렬해준다.
def drive():
now_length = 0
now_index = 0
moved_distance[0] = 0
while now_length < d:
while now_index < n:
start, end, length = (graph[now_index])[0], (graph[now_index])[1], (graph[now_index])[2]
if start != now_length:
break
if end <= d:
# 비교해서 이동 거리가 더 적으면 지름길로 이동
compare = moved_distance[now_length] + length
if compare < moved_distance[end]:
moved_distance[end] = compare
now_index += 1
# 비교해서 다음칸의 값이 더 작으면 한칸 이동해준 값을 넣어준다.
if moved_distance[now_length] + 1 < moved_distance[now_length + 1] :
moved_distance[now_length + 1] = moved_distance[now_length] + 1
now_length += 1
print(moved_distance[d])
drive()