[백준] 9665번 - 지름길 문제

 

문제

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

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

입력

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

출력

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

 

풀이) 왜 다익스트라 대신 DP를 선택했을까?

지름길 문제는 고속도로의 시작점에서 도착점까지 가는 최단 거리를 구하는 문제이다. 최단 거리라는 키워드를 보자마자 가장 먼저 다익스트라와 DP 가 떠올랐다. 아래 두개의 알고리즘을 비교하여 선택한 계기를 작성하였다.

1. 다익스트라 알고리즘이란?

다익스트라는 현재 갈 수 있는 곳 중 가장 가까운 곳부터 확정 짓는 그리디 방식의 알고리즘이다.

• 원리:
  1. 시작점에서 갈 수 있는 노드들의 거리를 갱신한다.
  2. 아직 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택한다.
  3. 그 노드를 거쳐서 다른 노드로 가는 것이 더 빠른지 계산하고 갱신한다.
  4. 목적지에 도달할 때까지 반복한다.
• 특징: 노드 간의 연결이 복잡하게 얽혀 있어도 최단 거리를 정확히 찾아낸다. 시간 복잡도는 O(ElogV) (E: 간선 수, V: 노드 수)

2. 다이나믹 프로그래밍 (DP) 란?

DP는 큰 문제를 작은 문제로 쪼개서 푸는방식이다. 작은 문제의 답을 구하고, 그 답을 저장해두었다가 다음 문제를 풀 때 재사용한다.

• 작동 원리:
  1. 문제를 순차적인 단계(State)로 나눈다.
  2. 이전 단계의 정답을 이용해 현재 단계의 정답을 도출하는 점화식을 세운다.
  3. 초기값부터 목표값까지 순서대로 채워 나간다.
• 예를 들어 계단 오르기 문제에서 10번째 계단까지 가는 최소 힘을 구하려면, 9번째 계단까지의 최소 힘과 8번째 계단까지의 최소 힘을 알면된다. 즉, f(n) = min(f(n-1), f(n-2)) + cost 같은 식을 세워 계산해야할 경우 dp 를 사용한다.
• 특징: 부분 문제의 최적해가 전체 문제의 최적해가 될 때 사용한다.

3. 왜 DP를 선택했는가?

이유 1: 단방향 조건과 순서가 보장된다

이 문제의 고속도로는 0에서 D 방향으로만 흐른다. 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)이다.

다익스트라는 어디가 가장 가까운지를 찾기 위해 우선순위 큐를 뒤적거려야 하지만, DP는 그냥 고속도로 시작부터 끝까지 1km씩 훑으면서 내려가면 된다.

이유 2: 구현의 단순함과 효율성

• 다익스트라: 우선순위 큐(heapq)를 import하고, 노드 방문 처리를 하고, 큐가 빌 때까지 while문을 돌려야 한다.
• DP: 그냥 for문 하나로 0부터 D까지 돌면 된다.

시간 복잡도 측면에서도, 다익스트라는 간선이 많아질수록 큐 연산 비용이 들지만, 이 방식의 DP는 O(D + N)으로, 거리만큼 한 번만 반복하면 되므로 매우 가볍다.

4. 코드 구현

# N: 지름길 개수, D: 고속도로 길이
N, D = map(int, input().split())

# dp[i]: 0에서 i까지 가는 최소 거리
# 일단은 지름길 없이 1km씩 걸어가는 것으로 초기화
dp = [i for i in range(D + 1)]

# 지름길 정보 저장
shortcuts = [[] for _ in range(D + 1)]
for _ in range(N):
    start, end, length = map(int, input().split())
    # 유효한 지름길만 저장 (역주행 불가, 지름길이 더 멀면 무시)
    if end <= D and end - start > length:
        shortcuts[start].append((end, length))

# 0부터 D까지 거리 순으로 스캔
for i in range(D):
    # 1km 그냥 가는 경우
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)

    # i에서 시작하는 지름길들
    for end, length in shortcuts[i]:
        dp[end] = min(dp[end], dp[i] + length)

5. 결론

문제를 만났을 때 무조건 최단 거리 = 다익스트라라고 단정 짓기보다는, 그래프의 형태를 먼저 파악하는 것이 중요하다.

이번 문제처럼 방향이 정해져 있고 순환하지 않는 구조라면, 복잡한 자료구조 없이 DP를 이용해 앞에서부터 차근차근 채워 나가는 것이 훨씬 직관적이고 효율적이다.