[ 백준 / 1446 ] 지름길 (Python)

https://www.acmicpc.net/problem/1446

 

난이도 : 실버 1 
알고리즘 유형 : DP 
풀이 시간 : 18분 

문제 풀이 

D킬로미터 길이의 고속도로를 지나는 데 운전해야하는 거리의 최솟값을 출력하는 문제이다. 

고속도로를 지나는 데에는 몇 개의 지름길이 존재한다. 그 지름길을 활용하면 최소한의 거리로 D킬로미터의 고속도로를 통과할 수 있다.

 

문제에서 모든 지름길은 일방통행이고, 고속도로는 역주행할 수 없다고 하였다. 여기서 우리는 현재 계산한 결과가 이전 결과에 영향을 미치지 않는다는 것을 파악할 수 있다. 또한, 최솟값을 출력하라고 하였으므로, 우리는 무난하게 Bottom-Up 방식의 DP 알고리즘을 활용할 수 있다.

 

문제를 풀며 주의해야 할 부분은, 지름길의 출발지 도착지가 중복될 수도 있다는 점이다. $N ≤ 12$로 주어졌기 때문에 2중 반복문으로 풀어도 시간복잡도가 터지지 않는다. ($O(12 * 10001)$)

 

따라서, 문제는 다음과 같은 방식으로 풀었다.

1. 1킬로미터씩 이동하면서 DP를 업데이트 해준다. `dp[i] = min(dp[i], dp[i - 1] + 1)`

2. 만약 현재 위치를 출발지로 하는 새로운 지름길이 존재하는 경우, 도착지까지의 dp 배열을 미리 업데이트 해주었다.

for s, e, l in short_road:
    if i == s:
        dp[e] = min(dp[e], dp[i] + l)

 

dp 배열을 생성해줄 때에는 최대 범위인 10001칸을 생성해주어 out of range 에러를 방지해주었다.

 

코드

'''
D 킬로미터 길이의 고속도로를 지난다.
고속도로에는 지름길이 존재함

운전해야 하는 거리의 최솟값

풀이 : LIS처럼 풀면 괜찮을 것 같다.
최대 거리 <= 10000 이고, 단방향 이동이 가능하기 때문에, DP로 문제해결 가능해보임
고속도로의 길이를 탐색하며, 지름길이 있는 경우에 대해 최솟값을 저장해주는 방식의 bottom - up
'''

import sys
input = sys.stdin.readline


def solution():
    n, m = map(int, input().split())
    short_road = [tuple(map(int, input().split())) for _ in range(n)]
    dp = [int(1e9)] * 10001

    # dp시작
    dp[0] = 0
    for s, e, l in short_road:
        if not s:
            dp[e] = min(dp[e], dp[0] + l)
    for i in range(1, m + 1):
        dp[i] = min(dp[i], dp[i - 1] + 1)
        for s, e, l in short_road:
            if i == s:
                dp[e] = min(dp[e], dp[i] + l)

    print(dp[m])

if __name__ == '__main__':
    solution()

배운 점 

이전에 풀었던 방법을 다시 한 번 봤는데, 출발지에서 지름길 여부를 판단하는 것이 아니라, 도착지에서 지름길 여부를 판단하고 있었다. 

도착지에서 판단하는 경우, 출발지에서 시작되는 불필요한 for문을 사용하지 않아도 되고, dp 배열을 업데이트 할 때, 굳이 `min()`을 두 번 사용하지 않아도 되어 시간복잡도의 효율이 올라가있었다.

이런 부분에 대해 생각하지 않고 풀었었는데, 문제를 어떻게 효율적으로 풀어나갈지에 대해 항상 고민하고 생각하며 풀어야겠다.