[baekjoon] 백준 1446번(파이썬): 지름길

문제

1446번: 지름길

알고리즘

- bfs 탐색으로 문제를 수행한다.

- 0부터 고속도로의 길이까지 반복하여 최단 거리를 구한다.

- 지름길로 간 거리와 고속도로로 간 거리를 비교하여 최단 거리를 입력한다.

- 지름길을 반복하여 최단 거리를 찾는다.

코드

import sys

n, d = map(int, sys.stdin.readline().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dis = [i for i in range(d+1)]

# 0 부터 고속도로의 길이까지 반복하여 확인
for i in range(d+1):

    # 지름길로 간 거리와 고속도로로 간 거리를 비교
    dis[i] = min(dis[i], dis[i-1]+1)

    # 지름길을 반복하여 최단 거리를 찾는다.
    for s, e, shortcut in graph:
        if i == s and e <= d and dis[i]+shortcut < dis[e]:
            dis[e] = dis[i]+shortcut

# 고속도로의 끝에 도착했을 때까지 걸린 거리를 출력
print(dis[d])

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법