B)1446

지름길

문제

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

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

입력

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

출력

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

원래 다익스트라로 푸는 문제인진 잘 모르겠지만, 다익스트라 개념을 공부하고 이 문제를 보니, 풀 수 있을 것 같은 느낌이 들어서, 한번 이용해보기로 했다.
결국, 지름길을 통해서 해당 좌표로 가게 되면, 그게 최단거리가 되는 것 이라고 생각했기 때문이다.

구현(Dijkstra)
1.목표 지점까지 이어진 그래프를 만든다.
2.간선간의 가중치를 1로 두고, 지름길은 따로 가중치를 갖도록 한다.
3.목적지 까지의 최단 거리를 구한다.

코드로 살펴보자

import sys
import heapq

input = sys.stdin.readline
n, d = map(int,input().split())
INF = 1000000000
distance = [INF] * (d+1)
graph = [[]for i in range(10001)] #최댓값이 주어졌기 때문에.
for i in range(d):
    graph[i].append((i+1,1)) #단방향으로 그래프를 잇고, 노드당 시간을 1로 설정
for _ in range(n):
    u,v,c = map(int,input().split())
    if v > d : #지름길을 탔을 때, 목적지를 벗어나게 된다면
        continue
    graph[u].append((v,c)) #지름길 시간 설정

def dijkstra(start):
    queue = []
    heapq.heappush(queue,(0,start))
    distance[start] = 0
    while queue:
        dist, node = heapq.heappop(queue)
        if distance[node] < dist:
            continue
        for next in graph[node]:
            cost = distance[node] + next[1]
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                heapq.heappush(queue,(cost,next[0]))


dijkstra(0)
print(distance[d])

지름길을 적절히 탔을 때의 시간이, 기존 시간보다 빠르게 갈 수 있기 때문에, 다익스트라 알고리즘을 적절히 사용하면 쉽게 풀 수 있는 문제였다.
하지만 최대 좌표가 이것보다 더 크거나, 많은 양의 데이터를 사용하게 되었을 때, 이 알고리즘을 사용해도 괜찮을지는 의문이다.
모든 그래프를 단방향으로 이어주는 과정에서 불필요한 시간이 걸리는 것은 아닌지 고민했지만, 문제를 푸는데는 지장은 없긴 했다.