졍's 기술 블로그

지름길

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 다이나믹 프로그래밍, 그래프 이론, 다익스트라

문제

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

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

입력

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

출력

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

예제 입출력

Algorithm

dijkstra 알고리즘 - 힙
1. 지름길을 입력 받아 graph 생성
    ➝ 도착 지점이 고속도로의 길이보다 큰 경우 graph에 추가하지 않음
2. 지름길이 아닌 길도 graph에 추가
    ➝ 중간에 끊겨있는 길도 같이 추가
3. D 위치의 최단 거리 출력

Code

import sys
import heapq

INF = int(1e9)
input = sys.stdin.readline

def dijkstra(start):
    queue = []
    
    # 첫 번째 칸으로 가는 최단 경로 0으로 설정
    heapq.heappush(queue, (start, 0))
    distance[start] = 0
    
    while queue:
        
        # 큐에서 꺼내기
        dist, now = heapq.heappop(queue)
        
        # 방문한 노드라면 무시
        if distance[now] < dist:
            continue
        
        # 인접 노드 확인
        for next in graph[now]:
            cost = dist + next[1]
            
            # cost가 인접노드까지 가는 데 최소 거리라면 갱신하고 큐에 추가
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                heapq.heappush(queue, (cost, next[0]))
    

N, D = map(int, input().split())
graph = [[] for _ in range(D+1)]
distance = [INF] * (D+1)
for _ in range(N):
    start, end, length = map(int, input().split())
    # 도착 지점이 고속도로의 길이보다 큰 경우 graph에 추가하지 않음
    if end > D:
        continue
    graph[start].append((end, length))

    # 지름길이 아닌 길도 graph에 추가
    if (end, end - start) not in graph[start]:
        graph[start].append((end, end - start))
        
for i in range(D):
    # graph의 현재 INDEX에 다음 칸 까지의 거리 추가
    graph[i].append((i+1, 1))

dijkstra(0)
print(distance[-1])

메모리: 32928 KB
시간: 72 ms