[ BOJ 1446 ] 지름길(Python)

문제

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()