[BOJ - 다익스트라] 1446번 : 지름길 (python)

 

백준 알고리즘 - 다익스트라  - 1446 지름길 파이썬

 

https://www.acmicpc.net/problem/1446

1446번: 지름길

 

문제

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

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

입력

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

출력

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

 

 

 

---

 

 

기본적인 다익스트라 문제를 풀고 응용겸 실버 1 문제를 풀어봐야지 했는데

역시 첫 응용이라 조건 생각하는게 너무 어려웠다.

 

 

그래서 다른 사람들의 글을 보며 조건을 어떻게 생각했는지 참고를 했다.

 

1) 세준이는 0애서 시작, D킬로미터까지 가야한다.

2) D가 10000보다 작거나 같기 때문에 D까지의 거리 하나하나를 노드로 보면된다.

3) 노드로 보았을때 일단 최소 거리는 for 문을 통해 1로 초기화해준다. (노드 i 에서 다음 노드 i+1까지의 거리는 1)

4) 이후 지름길의 정보가 들어오면 graph에 정보를 추가한다.

만약 지름길의 정보에서 지름길이 끝나는지점이 목표지점 D보다 크면 (뒤로 돌아갈 수 없는 고속도로이므로) 정보를 추가하지 않는다.

 

 

 

나머지는 기본적인 다익스트라랑 똑같다.

다익스트라(0)을 동작시키고,

 

distance[D] 를 출력해서 최소비용을 출력하면 정답!

 

#1446_지름길_다익스트라_silver1

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9)

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)

        #지금 힙큐에서 뺀게 now까지 가는데 최소비용이 아닐수도 있으니 체크
        if dist > distance[now]:
            continue

        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost, i[0]))


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

#일단 거리 1로 초기화.
for i in range(d):
    graph[i].append((i+1, 1))

#지름길 있는 경우에 업데이트
for _ in range(n):
    s, e, l = map(int,input().split())
    if e > d:# 고려 안해도 됨.
        continue
    graph[s].append((e,l))

dijkstra(0)
print(distance[d])