[백준] 1446: 지름길 JAVA

접근

처음에 보았을 때는 문제가 잘 이해되지 않았는데, 고속도로가 없는 구간은 길이의 차이만큼 운전해서 간다는 사실을 뒤늦게 이해했다. 사실 이번 문제는 많이 헤매서 이게 괜찮은 코드인지는 잘 감이 안온다.. 다익스트라 알고리즘을 풀려고 고른 문제이지만 dp로도 풀 수 있다고 한다. 

 

일단 이 문제에서 신경써야할 부분은 "입력으로 들어오는 지름길이 최단거리가 아닐 수도 있다"는 점이다. 그리고 지름길의 도착 지점이 d값을 넘어간다면 결국 쓸모없는 데이터이므로, 입력값을 받을 때 이 두 경우를 고려해서 처리해줬다. 그렇게 값을 저장한 후, 다익스트라 함수에서는 출발 지점을 기준으로 정렬하는 PQ를 사용했다. d의 범위를 벗어나거나 거리가 갱신되지 않는 경우는 넘어가고 나머지는 새로운 값을 넣어준다. 이 때, 지름길이 있어도 +1칸으로 이동하는게 추후에 이득인 경우도 있으므로 지름길의 여부와 상관없이 한 칸 이동한 값을 함께 넣는다. 그리고 마지막에 결과값을 출력할 때, dist 배열을 -1로 초기화했기 때문에 dist[d]에서 1을 더해주도록 했다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ1446 {
    static class Road implements Comparable<Road> {
        int from, to, cost;

        public Road(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

        @Override
        // 출발 지점이 작은 것부터 정렬
        public int compareTo(Road o) {
            return this.from - o.from;
        }
    }

    static int INF = 10001;
    static ArrayList<ArrayList<Road>> graph;

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

        // 입력값 저장 및 초기값 설정
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        int[] dist = new int[INF];

        for (int i = 0; i < INF; i++)
            graph.add(new ArrayList<>());
        Arrays.fill(dist, -1);

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            // 도착 지점을 넘어가는 지름길은 의미 없음 & 지름길이 항상 최단인 것은 아님
            if(to > d || cost >= to - from) continue;
            graph.get(from).add(new Road(from, to, cost));
        }

        dijkstra(dist, d);

        // 결과 출력(dist[0]이 -1이므로 1 증가시켜 출력)
        System.out.println(dist[d] + 1);
    }

    static void dijkstra(int[] dist, int d){
        PriorityQueue<Road> pq = new PriorityQueue<>();
        pq.add(new Road(0, 0, 0));
        dist[0] = -1;

        while(!pq.isEmpty()){
            Road cur = pq.poll();

            // 범위를 벗어남
            if(cur.to > d) continue;
            // 거리가 갱신되지 않음
            if(dist[cur.to] != -1 && dist[cur.to] < dist[cur.from] + cur.cost) continue;

            // 최단 거리 갱신
            dist[cur.to] = dist[cur.from] + cur.cost;

            // 지름길 이용
            for(Road road : graph.get(cur.to))
                pq.add(new Road(road.from, road.to, road.cost));

            // 한 칸 이동
            pq.add(new Road(cur.to, cur.to+1, 1));
        }
    }
}