[백준] 1446 파이썬

문제

---

• 백준 1446 (실버 1)

백준 1446

d킬로미터까지 이동해야 하는데 n개의 지름길이 주어질 때, 이동해야하는 최소 거리를 구하는 문제였다.
이동은 단방향으로만 가능하고 역주행은 안된다는 것이 문제의 조건이였다.
n이 최대 12까지여서 시간복잡도는 널널한 문제였다.

내 코드

---

우선은 dp가 가장 먼저 떠올라서 해당 방식으로 구현해보았다.
가장 먼저 입력받을 때에 지름길의 역할을 하지 못하는 입력과, 도착 지점이 d보다 큰 입력들을 걸러서 받아주었다.
그리고 중간에 거치는 지점들을 dp의 노드로 잡아주었다.
각 지름길을 탐색하면서 해당 지름길을 포함하면서 각 노드까지의 최소거리를 계속 업데이트하는 방식으로 구현하였다.
구현하고 보니 dp라고 보기는 조금 애매한 느낌이였다.

import sys
input = sys.stdin.readline

n, d = map(int, input().split())
dp = {}
dp[0] = 0
dp[d] = d
roads = []
for i in range(n):
    a, b, c = map(int, input().split())
    if 0 <= a <= d and 0 <= b <= d:
        if b - a > c:
            dp[a] = a
            dp[b] = b
            roads.append((a, b, c))
roads.sort()

for a, b, c in roads:
    if dp[a] + c < dp[b]:
        dp[b] = dp[a] + c
        for k in dp.keys():
            if k > b:
                if dp[b] + k - b < dp[k]:
                    dp[k] = dp[b] + k - b

print(dp[d])

다른 사람들의 코드를 보니 다익스트라 알고리즘을 통해서 구현한 것을 볼 수 있었다.
문제를 풀 때 다익스트라를 잘 떠올리지는 못하는 것 같아 더 익숙해지도록 연습해야 겠다.