BJ G5 1446 지름길

BJ G5 1446 지름길

 

 

문제링크

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

1446번: 지름길

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

youtu.be/W1XliXTM4ic

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ_G5_1446_지름길2 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    static int N;
    static int D;

    static List<ShortPath> paths;

    static Pair[] pairs;

    static int INF = 987654321;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));

        StringTokenizer tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        D = Integer.parseInt(tokens.nextToken());

        paths = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(input.readLine());
            int from = Integer.parseInt(tokens.nextToken());
            int to = Integer.parseInt(tokens.nextToken());
            int dist = Integer.parseInt(tokens.nextToken());
            // 역주행은 할 수 없다.: D 이내여야 가능
            if (to > D) {
                continue;
            }
            // 지름길은 지름길이어야지..
            if (dist >= (to - from)) {
                continue;
            }
            paths.add(new ShortPath(from, to, dist));
        }
        // 탐색 시작
        pairs = new Pair[D + 1];
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        for (int i = 0; i < pairs.length; i++) {
            Pair p = new Pair(i, INF);
            pairs[i] = p;
            if (i == 0) {
                p.dist = 0;
                pq.offer(p);
            }
        }

        // 출발 지점 초기화
        while (!pq.isEmpty()) {
            Pair front = pq.poll();
            if (front.no == D) {
                break;
            }

            // 다음 자식은: 1칸 가거나 지름길 있으면 그걸로 가거나.
            Pair next = pairs[front.no + 1];
            if (next.dist > front.dist + 1) {
                next.dist = front.dist + 1;
                pq.offer(next);
            }

            // 지름길 있으면 그쪽으로 가봐?
            for (ShortPath path : paths) {
                if (path.from == front.no) {
                    Pair spNext = pairs[path.to];
                    if (spNext.dist > front.dist + path.dist) {
                        spNext.dist = front.dist + path.dist;
                        pq.offer(spNext);
                    }
                }
            }
        }

        System.out.println(pairs[D].dist);
    }

    static class Pair implements Comparable<Pair> {
        int no, dist;

        public Pair(int no, int dist) {
            this.no = no;
            this.dist = dist;
        }

        @Override
        public int compareTo(Pair o) {
            return Integer.compare(this.dist, o.dist);
        }
    }

    static class ShortPath {
        int from;
        int to;
        int dist;

        public ShortPath(int from, int to, int dist) {
            this.from = from;
            this.to = to;
            this.dist = dist;
        }
    }

    private static String src = "5 150\r\n" +
                                "0 50 10\r\n" +
                                "0 50 20\r\n" + // 더 긴 지름길이 왠말이냐..
                                "50 100 10\r\n" +
                                "50 151 10\r\n" + // 역주행은 안되니까 151은 의미 없다.
                                "110 140 10"; // 이게 무슨 지름길이냐?
}