[백준][Python] 1446번. 지름길 (실버1)

!https://d2gd6pc034wcta.cloudfront.net/tier/10.svg

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

128 MB

11450

6486

4939

57.178%

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 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

출처

• 문제를 번역한 사람: baekjoon
• 문제를 다시 작성한 사람: jh05013

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 데이크스트라
• 최단 경로

아이디어

다익스트라를 파이썬에서 써본 적이 없어서 다익스트라 알고리을 이용해서 구현해보았다.

문제 풀이

'''
백준 실버1
1446번
지름길
'''
import sys
import heapq

N, D = map(int, sys.stdin.readline().split())

# 지름길 정보를 담을 리스트
shortcuts = []

for _ in range(N):
    depart, arrive, length = map(int, sys.stdin.readline().split())
    if arrive - depart > length and arrive <= D:
        shortcuts.append((depart, arrive, length))

# 출발위치 오름차순 + 도착위치 내림차순으로 정렬
shortcuts.sort(key=lambda s: (s[0], -s[1]))

# 거리 배열, 초기값은 최대로 설정
distance = [i for i in range(D + 1)]

# 다익스트라 알고리즘을 활용한 최단거리 계산
for i in range(D + 1):
    if i != 0:
        distance[i] = min(distance[i], distance[i - 1] + 1)  # 현재 위치까지의 거리 업데이트

    for depart, arrive, length in shortcuts:
        if depart == i and arrive <= D:
            distance[arrive] = min(distance[arrive], distance[depart] + length)

print(distance[D])