[BOJ_Python] 1446. 지름길

문제

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

사용 알고리즘

DP

 

풀이

고려사항

1. 지름길 관리 방법

2. 바로 전에 길에서 온 값과 현재 길에 적혀있는 값 비교

3. 현재 지점에서 갈 수 있는 지름길 탐색

 

후기

1. 이 문제의 keypoint는 지름길 사용 유무에 따른 값 갱신이다.

 

2. 현재 위치에서 가지고 있는 값과 이전 값에서 오는 값을 비교하여 갱신을 진행한다.

일반 도로 이동 → dp[cur] = dp[cur-1] + 1

    - 지름길을 사용하지 않고 이전 길에서 오는 것 : 이전 값에서 1km 더 온 것으로 "이전 값 + 1"

현재 위치에서 최소값 → dp[cur] 

    - 지름길로 온 값 : 이미 출발점에서 온 값으로 갱신 되어 있는 값

 

3. 이후 현재 위치에서 갈 수 있는 지름길을 탐색하여 그 위치의 값과 비교하여 갱신을 진행한다.

지름길 적용 → 출발점이 cur인 지름길을 이용하여 dp[도착점]을 갱신

 

4. 이때, 지름길은 list와 lambda를 사용하여 관리하였다.

- 딕셔너리는 중복 값이 있어 초기 세팅에 불리하였다.

- 정렬이 없는 리스트는 순서가 보장되지 않기 때문에

  매 위치마다 지름길을 모두 탐색해야한다.

  특히, 이 문제의 경우 현재 위치에서 갈 수 있는 지름길이

  한 개로 정해지지 않았기 때문에 중간에 끊을 수도 없다.

  때문에 시간관리 측면에서 불리하였다.

- heapq 방식도 고려했으나,

  이 문제의 경우 매번 지름길이 생기거나 값이 변하지 않기 때문에 불필요한 정렬을 줄이고

  매번 heappop과 사용하지 않았을 경우 발생되는 heappush가

  꼭 필요하지 않다고 생각되어 사용하지 않았다.

- 출발점 기준으로 지름길을 탐색할 것이고 역주행을 하지않아 이미 사용한 것을 보지 않아도 되기 때문에

  list와 lambda 방식으로 출발점을 기준으로 정렬한 방식으로 지름길을 관리하였다.

  예상 시간복잡도 : O(NlogN)

- 이때, 현재 위치에서 지름길이 여러개 일 수 있어 while을 통해 다음 위치를 만날때까지 진행해주었다.

- 또한, 마지막의 경우까지 지름길을 탐색했다면 이후에 index error가 발생할 수 있다.

  이 에러를 방지하기 위해 절대 만나지 않을 값(도착점보다 10 큰 값)을

  지름길 리스트에 더해주어 관리하였다.

  

5. index 관련 문제는 시작할 때도 발생 할 수 있었다.

일반도로를 이용한 경우 이전값과 비교해야하기 때문에 이전값이 존재해야한다.

때문에 [0]보다 전의 [0]을 하나 더 넣어주고 관리하였다.

이런 경우 기본 세팅해주고 시작하는거보다 일반화 할 수 있어 편했지만

뒤에 인덱스 관리 할 때 헷갈리지 않게 주의가 필요했다. 

 

코드

import sys
input = sys.stdin.readline

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

shortcuts = [list(map(int, input().split())) for _ in range(N)] + [[D + 10, 0, 0]]
shortcuts.sort(key=lambda x: x)

dp = [0] + [i for i in range(D + 1)]
s_idx = 0

for cur in range(1, D + 2):
    # 이전 값과 비교하여 현재 값 갱신
    dp[cur] = min(dp[cur - 1] + 1, dp[cur])

    # 지름길을 활용한 값 갱신
    while shortcuts[s_idx][0] == cur - 1:
        if shortcuts[s_idx][1] <= D:
            dp[shortcuts[s_idx][1] + 1] = min(
                dp[shortcuts[s_idx][1] + 1], dp[cur] + shortcuts[s_idx][2]
            )
        s_idx += 1


print(dp[D + 1])

 

결과