백준 | 지름길

백준 지름길

문제

일방 통행으로 역주행 불가능한 길이 d의 고속도로와 n개의 지름길이 주어질 때, 위치 0에서 출발하여 위치 d에 도달하기 위한 최단 거리를 구하는 문제이다.

조건은 다음과 같다.

[1] n은 12 이하의 자연수이고, d는 10,000 이하의 자연수이다.
[2] 모든 위치와 길이는 10,000 이하의 음이 아닌 정수이다.
[3] 지름길의 시작 위치는 도착 위치보다 작다.

풀이

만약 일반 도로로 이동한 거리보다 지름길의 거리가 길다면, 최단 거리랑은 상관없는 길이므로 고려할 필요가 없다.

따라서 지름길의 정보(시작점, 도착점, 거리)를 저장할 shortcuts이라는 리스트에 일반 도로보다 길거나 같은 지름길은 저장하지 않았다.

shortcuts = []
for _ in range(n):
    start, end, shortcut = map(int, sys.stdin.readline().split())

    # 지름길이 유효한 경우만 저장
    if end - start > shortcut:
        shortcuts.append([start, end, shortcut])

이제 위치 d까지 도달하기 위한 최단 거리를 구해야 한다.

어떤 위치 i까지 도달하는 방법은 일반 도로를 이용하거나, 지름길로 달리는 2가지 경우만 존재한다.

dp[i]를 위치 i까지의 최단 거리라고 정의했을 때, 위의 2가지 경우에 대한 점화식을 세울 수 있으므로 DP로 접근했다.

[1] 위치 (i - 1)에서 1만큼 이동해 위치 i에 도달하는 경우
[2] 어떤 위치에서 위치 i까지 지름길로 이동하는 경우

[1]은 for 문을 돌면서 min(dp[i], dp[i - 1] + 1)를 기준으로 업데이트하면 된다.

반면 [2]는 이전에 저장한 지름길들(shortcuts) 중에서 도착점이 end랑 일치하는 경우만 고려를 해야 하므로, end == i라는 조건이 필요하다. (이 조건에 의해 지름길이라고 하더라도 도착점이 d보다 먼 경우는 배제될 것이다.)

dp = [i for i in range(d + 1)]
for i in range(1, d + 1):
    # 1. 위치 (i - 1)에서 위치 i까지 기본 도로로 이동하는 경우
    dp[i] = min(dp[i], dp[i - 1] + 1)

    # 2. 위치 (i - 1)에서 위치 i까지 지름길로 이동 가능한 경우
    for start, end, shortcut in shortcuts:
        if end == i:
            dp[end] = min(dp[end], dp[start] + shortcut)

최종적으로 구하고자 하는 값은 위치 d까지의 최단 거리이므로 dp[d]를 출력하면 된다.

코드

import sys


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

shortcuts = []
for _ in range(n):
    start, end, shortcut = map(int, sys.stdin.readline().split())

    # 지름길이 유효한 경우만 저장
    if end - start > shortcut:
        shortcuts.append([start, end, shortcut])

# dp[i]: 위치 i까지의 최단 거리
dp = [i for i in range(d + 1)]
for i in range(1, d + 1):
    # 1. 위치 (i - 1)에서 위치 i까지 기본 도로로 이동하는 경우
    dp[i] = min(dp[i], dp[i - 1] + 1)

    # 2. 위치 (i - 1)에서 위치 i까지 지름길로 이동 가능한 경우
    for start, end, shortcut in shortcuts:
        if end == i:
            dp[end] = min(dp[end], dp[start] + shortcut)

print(dp[d])