[백준] 1446 지름길 - python

문제 링크

이 문제는 다익스트라 알고리즘을 사용해서 푸는 거라고 한다..
다익스트라 알고리즘을 어디선가 (아마 수업시간에) 배운 것 같은데 어떤 것인지 기억이 잘 나지 않았다.

다익스트라 알고리즘

다익스트라 알고리즘은 주로 최단 경로를 찾는 데에 쓰인다.
모든 노드의 가중치를 INF로 설정하고, 주어진 경로가 노드의 가중치보다 작으면 해당 경로를 최적의 경로라고 설정하는 것이다.

어떤 절차로 업데이트하는 지는 이 페이지를 확인하면 쉽게 알 수 있다.

해결

다익스트라 알고리즘이 잘 생각이 나지 않아서, 나는 그냥 다익스트라를 사용하지 않고 풀었다.

# 지름길
import sys
input = sys.stdin.readline
n, d = map(int, input().rstrip().split(' '))

graph = []
for _ in range(n):
    graph.append(list(map(int, input().rstrip().split(' '))))

distance = [i for i in range(d+1)]

for i in range(d+1):
    distance[i] = min(distance[i], distance[i-1]+1)
    for start, end, dist in graph:
        if i == start and end <= d and distance[i] + dist < distance[end]:
            distance[end] = distance[start] + dist

print(distance[d])

이것도 블로그를 보고 참고하였다.

나는 30분 이상 생각해보고 안 나오는 거는 블로그를 찾아보는 편인데,
블로그를 찾아볼 때마다 좀...자신감이 떨어지는 것 같다.
나도 생각은 비슷하게 했는데 이것이 깔끔하지 않거나, 코드로 잘 구현되지 않는다.
앞으로 더 해보면 늘겠지..?