BOJ 1446 지름길

https://www.acmicpc.net/problem/1446

문제

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

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

---

입력

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

---

출력

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

---

예제 입력 1

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

예제 출력 1

70

예제 입력 2

2 100
10 60 40
50 90 20

예제 출력 2

80

… 이하 예제 생략

---

코드

DP로 문제를 풀었다.
풀고 나니 다익스트라 카테고리도 붙어 있어서 잠깐 이에 대해 생각해봤다.
각 지름길의 종료 지점부터 이후의 모든 위치까지의 최단 거리를 계산하는 방식으로도 볼 수 있어서 다익스트라 문제라고도 볼 수 있을 것 같다.

풀이 과정은 다음과 같다.

1. 지름길의 도착 위치를 기준으로 오름차순 검사를 하기 위해 우선순위 큐에 지름길 정보들을 offer 한다.
2. 우선순위 큐에서 지름길 정보를 하나씩 poll 해서 다음과 같은 작업을 수행한다.

   2-1. 지름길의 도착 위치가 D보다 크면 이후 작업을 생략한다.
   2-2. 해당 지름길의 도착 위치부터 D까지 해당 지름길을 이용했을 때의 최소 이동 거리를 계산한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static class ShortCut {
        int start;
        int end;
        int dis;

        public ShortCut(int start, int end, int dis) {
            this.start = start;
            this.end = end;
            this.dis = dis;
        }
    }

    static int N;
    static int D;

    static int[] distance;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        distance = new int[D + 1];
        for (int i = 1; i <= D; i++) {
            distance[i] = i;
        }

        PriorityQueue<ShortCut> shortCuts = new PriorityQueue<>(Comparator.comparingInt(s -> s.end));
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int dis = Integer.parseInt(st.nextToken());

            shortCuts.offer(new ShortCut(start, end, dis));
        }

        while (!shortCuts.isEmpty()) {
            ShortCut shortCut = shortCuts.poll();
            calculateMinDistance(shortCut.start, shortCut.end, shortCut.dis);
        }

        System.out.println(distance[D]);
    }

    static void calculateMinDistance(int start, int end, int dis) {
        if(end > D) {
            return;
        }

        int startDistance = distance[start] + dis;

        for (int i = end; i <= D; i++) {
            distance[i] = Math.min(distance[i], startDistance);
            startDistance++;
        }
    }
}