문제

문제 설명

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

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

---

Java

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int d=Integer.parseInt(st.nextToken());

        //[시작 지점, 목표 지점, 비용]
        int[][] shortcuts=new int[n][3];
        for(int i=0; i<n; i++){
            st=new StringTokenizer(br.readLine());
            shortcuts[i][0]=Integer.parseInt(st.nextToken());
            shortcuts[i][1]=Integer.parseInt(st.nextToken());
            shortcuts[i][2]=Integer.parseInt(st.nextToken());
        }

        //시작 지점을 기준으로 지름길 정렬
        Arrays.sort(shortcuts, Comparator.comparingInt(o->o[0]));
        //[현재 위치, 비용]의 형태로 우선순위큐 삽입, 정렬 기준:비용
        PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(o->o[1]));
        pq.add(new int[]{0, 0});
        while(!pq.isEmpty()){
            int[] ptr=pq.poll();
            int location=ptr[0];
            int cost=ptr[1];

            if(location==d){
                System.out.println(cost);
                return;
            }

            //현재 위치와 지름길의 시작 지점이 같고, 지름길의 목표 지점이 D와 같거나 더 짧고, 지름길을 타는 것이 더 이득일 때 우선순위큐에 삽입
            int next=d;
            for(int[] i:shortcuts){
                if(i[0]>location) {     //지름길의 시작 지점이 현재 위치보다 크면 다음 목표 위치로 세팅하고 break
                    next = i[0];
                    break;
                }
                else if(i[0]==location){
                    if(i[1]<=d && i[1]-location>i[2])
                        pq.add(new int[]{i[1], cost+i[2]});
                }
            }
            //다음 목표지점, D 중 가까운 위치를 우선순위큐에 삽입
            pq.add(new int[]{Math.min(next, d), Math.min(next, d)-location+cost});
        }
    }
}

---

해결 과정

1. Dijkstra를 사용해서 매번 최소 비용의 노드를 선택해서 목적지를 도달한다. 지름길을 타는 것이 이득일 수도 있고, 아닐 수도 있기 때문에 지름길을 타서 가는 방법과 안 타는 방법 모두 우선순위 큐에 추가한다. 매번 노드마다 지름길들을 살펴보는데 지름길의 개수가 최대 12이기 때문에 무시할 수 있는 수준이다.

2. 😁