99클럽 코테 스터디 27일차 TIL - 지름길(백준 #1446)

❇️오늘의 학습 키워드 : 지름길(백준 #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

정답 코드

import sys, heapq

n, d = map(int, sys.stdin.readline().split())  # n: 지름길 개수, d: 고속도로 길이

# 그래프 초기화: d+1 길이의 빈 리스트 생성
graph = [[] for _ in range(d+1)]
dist = [float("inf")] * (d+1)  # 0부터 d까지 모든 지점의 최단 거리

# 기본적으로 1칸씩 이동하는 경우 추가
for i in range(d):
    graph[i].append((i+1, 1))  # i에서 i+1로 가는 거리는 항상 1

for _ in range(n):
    start, end, length = map(int, sys.stdin.readline().split())  # 시작점, 끝점, 지름길 길이
    if end <= d:  # 지름길의 끝점이 고속도로 길이를 넘어가지 않을 경우만 추가
        graph[start].append((end, length))

q = []
heapq.heappush(q, (0, 0))  # 시작점 (거리 0, 위치 0) 추가
dist[0] = 0  # 시작점의 최단 거리 초기화

while q:
    w1, now = heapq.heappop(q)  # 현재 노드와 그 거리(w1)를 꺼냄

    for nxt, w2 in graph[now]:  # 현재 노드 now와 연결된 노드 nxt와 그 거리 w2를 확인
        cost = dist[now] + w2  # 현재 노드를 거쳐 nxt로 가는 거리 계산
        if dist[nxt] > cost:  # 더 짧은 경로가 발견되면 업데이트
            dist[nxt] = cost
            heapq.heappush(q, (cost, nxt))  # 갱신된 거리와 노드를 큐에 추가

print(dist[d])

❇️오늘의 회고

  - 지름길을 이용한 경우와 이용하지 않은 경우를 비교해서 더 짧은 경로를 찾는 것이 중요하다. 

  - 항해99 코테스터디 덕분에 쉬는 날 없이 매일 알고리즘 공부를 할 수 있어서 좋은 것 같다. 벌써 약 일주일정도밖에 안남았는데 이 습관을 오래 유지할 수 있었으면 좋겠다...

  - 내일 11시, 문제를 풀기 전에 위 문제를 한번 더 복습하고 내일 문제에 사용된 알고리즘에 대해서 공부할 것이다!🙂