[백준] 1446 - 지름길

문제 설명

문제 링크

문제 풀이

최단거리 문제이다. 최단거리 문제를 풀지 않은지 오래되어 어떻게 하는지 까먹어서 일단 최대한 내가 생각해낼 수 있는 방법으로 진행하기로 했다.

우선 지름길의 시작점, 끝점, 거리를 받아 투플로 묶어 ‘지름길 배열’에 넣어줬다. 이 중에서 가장 효율적인 지름길 순으로 우선채택을 해야 할 것 같아 가장 효율적인 지름길을 찾는 알고리즘을 설계했다. 끝점 - 시작점(‘지름길이 없었다면 원래 가야할 거리’)에서 지름길의 거리를 빼주는 방식으로 했는데, 이 식을 사용했을 때 나오는 값은 ‘지름길을 사용함으로 단축한 거리’일 것이다. 지름길마다 이를 별도 배열 saved_dist에 저장하여 인덱스로 지름길 번호를 기억하기로 했다.

import sys
input = sys.stdin.readline

N, D = map(int, input().split())

shortcuts = []
shortest_order = [0] * (N)
saved_dist = 0

for i in range(N):
    start, end, dist = map(int, input().split())
    shortest_order[i] = (end - start) - dist
    shortcuts.append((start, end, dist))

그럼 이제 해야 할 것은 시작점과 끝점을 고려하여 어떤 지름길을 타야 하는지 결정하는 것이다. 다만, 이 시점부터는 머리가 꽤 아팠던 게, 어떻게 내가 실제로 이동한 구간을 저장할지 생각이 나지 않았다.

우선 주어진 예제를 기반으로 생각을 해보았을 때 만들어야 하는 조건문이 있다.

while True:
    index = shortest_order.index(max(shortest_order))
    if shortcuts[index][1] >= D:
        shortest_order[index] = 0
        continue

위와 같이 작성하면 지름길의 끝지점이 우리가 가고싶은 거리 이내에 있는지 확인할 수 있다. 아무리 거리를 획기적으로 줄여준다고 하더라도 단방향 고속도로에서 나가야하는 길목을 놓치면 남은 건 추가 톨비와 낭비된 시간 뿐이라는 것을 나는 실생활에서 너무나도 많이 경험해봤다 (이게 맞나?). 그럼으로 만약 끝지점이 우리의 도착지를 넘어간다면 ‘단축한 거리` 배열의 값을 0으로 줄여준다.

이제 남은 지름길들 중 어느 것들을 타고갈지 정해야 한다. 예제에 보면 시작점이 0이고 끝점이 50인 지름길이 두 개 있는데, 이 중 더 짧은 거리의 지름길을 선택해야 하는 것은 당연한데 이러한 방식으로는 답을 찾는 것이 불가능할 것 같다는 생각이 스멀스멀 들어 다시 시작해보았다.

결국 다익스트라 알고리즘을 한 번 다시 찾아보기로 했다.

코드