[BOJ_1446] 지름길

감이 안 잡혀서 많이 참고하고 풀어 본 문제다.

 

최소 거리를 저장하는 배열을 두고 from -> to 갈 곳이 없을 때 계속 한 칸씩 앞으로 가는 것을 구현해내면 완성 할 수 있다.

 

상세 설명은 아래 코드와 함께 주석으로 적었다.

 

package Graph;

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

public class BOJ_1446 {
    static class Data {
        int to;
        int w;

        public Data(int to, int w) {
            this.to = to;
            this.w = w;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine(), " ");

        int N = Integer.parseInt(tk.nextToken());
        int D = Integer.parseInt(tk.nextToken());

        List<Data>[] graph = new ArrayList[D + 1];
        for (int i = 0; i <= D; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            tk = new StringTokenizer(in.readLine(), " ");
            int from = Integer.parseInt(tk.nextToken());
            int to = Integer.parseInt(tk.nextToken());
            int w = Integer.parseInt(tk.nextToken());
            if (to <= D && to - from > w) { // 지름길을 이용하는 경우만 추가
                graph[from].add(new Data(to, w));
            }
        }

        int[] distance = new int[D + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0] = 0;

        PriorityQueue<Data> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.w, b.w));
        pq.offer(new Data(0, 0));

        while (!pq.isEmpty()) {
            Data curr = pq.poll();
            int currPos = curr.to;
            int currDist = curr.w;

            if (currDist > distance[currPos]) { //초기화가 이미 진행이 되었고 이미 들어온 거리가 더 짧다면 굳이 초기화 할 필요가 없음
                continue;
            }

            for (Data next : graph[currPos]) { // 그래서 이제 내가 보는 곳으로 부터 갈 수 있는 곳을 모두 탐색해보자.
                int nextPos = next.to;
                int nextDist = currDist + next.w;

                if (nextDist < distance[nextPos]) { // 만일 이전의 거리값이 더 크다면 초기화 해서 weight를 더 작은 수로 바꿀 수 있다.
                    distance[nextPos] = nextDist;
                    pq.offer(new Data(nextPos, nextDist));
                }
            }

            if (currPos + 1 <= D && currDist + 1 < distance[currPos + 1]) {
                // 한 칸씩 직진하면서 앞으로 가는 경우
                // 즉, from -> to 가 존재하지 않을 때 최소 거리를 계속 상승시켜 올라가는 부분이다.
                distance[currPos + 1] = currDist + 1;
                pq.offer(new Data(currPos + 1, currDist + 1));
            }
        }

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

 

1446번: 지름길