백준 1446번 - 지름길

지름길 문제 바로 가기

풀이 날짜: 2026-06-14

baekjoon 알고리즘 문제 풀이

풀이 코드


import heapq

n,d = map(int, input().split())
INF = int(1e9)

graph = [[] for i in range(d+1)]
distance = [INF] * (d+1)

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

for _ in range(n):
    start,end,l = map(int, input().split())

    if start > d or end > d:
        continue

    if end-start <= l:
        continue

    graph[start].append((end,l))

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

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

        for next_node, fee in graph[now]:

            cost = dist + fee
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(q,(cost,next_node))

dijkstra(0)

print(distance[d])

문제 접근

고속도로의 시작점 0에서 도착점 D까지 이동할 때 최단 거리를 구하는 문제이다. 처음에는 입력으로 주어지는 지름길만 그래프로 구성하여 다익스트라를 수행하려고 했지만, 실제로는 지름길뿐만 아니라 일반 고속도로 구간도 함께 고려해야 한다. 따라서 문제를 그래프로 모델링할 때 일반 도로와 지름길을 모두 간선으로 표현해야 한다는 점이 핵심이다.

핵심 아이디어

일반 고속도로는 현재 위치에서 다음 위치로 1만큼 이동할 수 있으므로, 모든 i(0 ≤ i < D)에 대해 i → i+1 비용 1의 간선을 추가한다. 이후 입력으로 주어지는 지름길은 start → end 비용 length의 간선으로 추가한다. 이렇게 하면 일반 도로와 지름길이 모두 포함된 그래프가 완성되며, 시작점 0에서 도착점 D까지의 최단 거리를 다익스트라 알고리즘으로 구할 수 있다.

구현 시 고려한 예외처

도착 지점을 넘어가는 지름길은 실제로 사용할 수 없으므로 무시하였다. 또한 지름길의 길이가 일반 도로를 이용하는 것보다 짧지 않은 경우에는 최단 경로 계산에 도움이 되지 않으므로 그래프에 추가하지 않았다. 이를 통해 불필요한 간선을 줄이고 탐색 효율을 높일 수 있었다.

if start >d or end > d: continue
if end - start <= length: continue

다익스트라 적용

우선순위 큐를 이용하여 현재까지의 최단 거리가 가장 짧은 노드부터 탐색하였다. 각 노드에서 연결된 다음 위치를 확인하며 비용을 갱신하고, 기존 거리보다 더 짧은 경로를 발견한 경우 거리 배열을 업데이트한 뒤 우선순위 큐에 다시 삽입하였다. 이를 반복하여 최종적으로 distance[d]에 저장된 값을 정답으로 출력하였다.

내가 헷갈렸던 부분

이 문제를 통해 다익스트라 알고리즘 자체보다 그래프 모델링의 중요성을 배울 수 있었다. 처음에는 지름길만 간선으로 추가했지만, 일반 도로 역시 이동 가능한 경로라는 사실을 그래프로 표현해야 올바른 최단 거리를 구할 수 있었다. 즉, 최단 경로 문제에서는 알고리즘 구현보다 “문제를 어떤 그래프로 표현할 것인가”가 더 중요할 수 있다는 점을 경험한 문제였다.

Vienna sausage