백준 - 지름길 1446 (Python)

[Silver I] 지름길 - 1446
https://www.acmicpc.net/problem/1446

 

문제설명

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

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

 

입력

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

 

출력

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

 

예제입력 / 예제출력

 

문제이해 및 코드설명

가장 짧은 경로를 찾는 알고리즘이라는 점에서 다익스트라 알고리즘을 사용한다는 점을 확인하였다.

다익스트라 알고리즘은 최단경로 알고리즘으로 특정 노드에서 다른 모든 노드로 가는 최단경로를 계산할때 사용한다.

특징으로는 음의간선을 사용할 수 없고 그리디 알고리즘(현재 상황에서 가장 좋은 최선의 선택을 고르는 알고리즘)으로 분류된다.

다익스트라는 다음과 같은 순서로 코드로 작성할 수 있다.

1. 출발노드를 설정
2. 최단 거리 테이블을 초기화( 모든 노드까지 가기 위한 비용 무한대, 자기자신 0으로 설정)
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택(그리디 알고리즘 특징)
4. 해당 노드 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블  갱신
5. 위 3,4,번 반복

이 문제에선 노드와 간선을 어떻게 설정하는지가 핵심이었던 문제이다. 시작노드를 0 , 도착노드를 D로 설정하고, 1,2,3,4...D-1를 모두 노드로 간주하기로 했다. 

 

 

코드

import sys
import heapq

# N,D 입력받음
N, D = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(D+1)]

for i in range(D):
    graph[i].append((i+1, 1))

for i in range(N):
    start, end, length = map(int, sys.stdin.readline().split())
    if end > D: continue
    graph[start].append((end, length))

INF = 987654321
distance = [INF]*(D+1)
distance[0] = 0

q = []
heapq.heappush(q, (0, 0))
while q:
    d, now = heapq.heappop(q)
    if distance[now] < d: continue

    for x in graph[now]:
        cost = d + x[1]

        if distance[x[0]] > cost:
            distance[x[0]] = cost
            heapq.heappush(q, (cost, x[0]))

print(distance[D])