[백준] 1446번 지름길 파이썬

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

예제 입력 1

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

예제 출력 1

70

예제 입력 2

2 100
10 60 40
50 90 20

예제 출력 2

80

예제 입력 3

8 900
0 10 9
20 60 45
80 190 100
50 70 15
160 180 14
140 160 14
420 901 5
450 900 0

예제 출력 3

432

문제풀이

• 기존에 알고있던 힙을 사용해서 푸는 다익스트라로는 풀이가 안 됐다.

• 그래서 다른 답안을 참고하였다.

• 참고 블로그 : https://fre2-dom.tistory.com/144

• 그래프 설정과 distance는 기존과 동일하게 해준다.

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

• 고속도로 길이만큼 for loop를 돌면서 길이를 갱신한다.
  • 지름길로 간 길이와 고속도로로 간 길이중에 작은 값을 i의 거리로 설정한다.
  • 만약에 i가 start랑 같고, end가 고속도로 길이보다 작으며, 현재까지 온 고속도로 길이랑 지름길이 end로 가는 고속도로 길이보다 짧으면 end로 가는 길의 거리를 업데이트 한다.

def solution():
    n, d = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(n)]
    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, short in graph:
            if i == start and end <= d and distance[i] + short < distance[end]:
                distance[end] = distance[i] + short

제출답안

import sys

input = sys.stdin.readline


def solution():
    n, d = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(n)]
    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, short in graph:
            if i == start and end <= d and distance[i] + short < distance[end]:
                distance[end] = distance[i] + short

    print(distance[d])


solution()