30869 : 빨리기다리기 Java

30869번- 빨리 기다리기

백준 아레나 신청해놓고 까먹고 있다가 부랴부랴 기억해서 참가했었다. 한 시간 반정도 남았을 때 도전했는데 처음 봤을 때는 쉽게 생각하고 BFS로 접근했었다. 제출하니까 시간 초과 뜨길래 다익스트라로 방향을 바꿨으나 시간이 없어서 못풀었었다. 그리고 다 풀고 나서 또 조건 제대로 안 읽어서 불가능할 경우 -1을 출력한다는 것을 못봤다. 그리고 나서는 ‘아 혹시 시간 합이 long이라서 그런가?’ 하고 엉뚱한 것만 손보고 있었다.

이것 때문에 한 15분 정도 더 해멨다..

결국 접근법 자체는 다익스트라가 맞았다. 대신 고려해야할 점이 빨리 기다리기인데 빨리 기다리기를 사용하면 배차간격을 무시하고 바로 탈 수 있다는 점이다.

예시로 바로본다면 ① -> ②로 가는 소요시간은 2시간이고 배차간격은 4시간이다. 이 경우에는 배차 간격을 기다릴 필요가 없이 바로 이동할 수 있으므로 ① -> ② 의 최단 시간은 2시간이다.

하지만 ② -> ③으로 갈 때는 배차시간이 적용된다. 2시간을 걸려서 ②까지 왔지만, ② -> ③으로 이동하기 위해서는 다음 배차까지 1시간을 기다려서 총 6시간(2 + 1 + 3)을 기다려야 한다. 이 때, 빨리 기다리기를 사용한다면, 1시간의 배차 시간을 무시하고 5시간에 이동할 수 있다.

구현은 벽 부수고 이동하기 시리즈와 비슷하다.
빨리 기다리기 개수인 K를 Route 클래스의 fastLeft로 뒀다. 다익스트라를 통해 이동 가능 경로를 비교해 배차시간까지 기다려야하는 시간이 0이라면 빨리 기다리기를 소모하지 않고 우선순위 큐에 삽입했다. 만약 기다려야 하는 시간이 0이상이고 빨리 기다리기를 사용할 수 있으면 빨리 기다리기를 사용한 뒤 우선순위 큐에 삽입했다. 그리고 이 때 둘 중 더 적은 시간을 저장했다.

이후에는 계속 비교하면서 빨리 기다리기를 사용한 것과 사용하지 않은 것중 최소 값을 저장한다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static List<Route>[] graph;
    static int[] dists;
    static int N, M, K;

    public static void main(String[] args) throws IOException {
        init();
        dijkstra();
        if (dists[N] == Integer.MAX_VALUE) {
            bw.write("-1");
        } else {
            bw.write(dists[N] + "");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static void init() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseUnsignedInt(st.nextToken());
        M = Integer.parseUnsignedInt(st.nextToken());
        K = Integer.parseUnsignedInt(st.nextToken());
        graph = new List[N + 1];
        for (int i = 1; i < N + 1; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken()),
                    t = Integer.parseInt(st.nextToken()), g = Integer.parseInt(st.nextToken());
            graph[s].add(new Route(e, t, g, K));
        }
        dists = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            dists[i] = Integer.MAX_VALUE;
        }
    }

    public static void dijkstra() {
        PriorityQueue<Route> pq = new PriorityQueue<>();
        pq.add(new Route(1, 0, 0, K));

        while (!pq.isEmpty()) {
            Route current = pq.poll();
            if (current.to == N) {
                continue;
            }

            for (Route next : graph[current.to]) {
                int waiting = (next.dispatch - (current.cost % next.dispatch)) % next.dispatch;
                int costSumWaiting = next.cost + waiting + current.cost;
                if (costSumWaiting < dists[next.to]) {
                    dists[next.to] = costSumWaiting;
                    pq.add(new Route(next.to, costSumWaiting, current.fastLeft));
                }
                if (waiting > 0 && current.fastLeft > 0 && dists[next.to] > costSumWaiting - waiting) {
                    dists[next.to] = costSumWaiting - waiting;
                    pq.add(new Route(next.to, costSumWaiting - waiting, current.fastLeft - 1));
                }
            }
        }
    }

}

class Route implements Comparable<Route> {
    int to;
    int cost;
    int dispatch;
    int fastLeft;

    public Route(int to, int cost, int repeat, int fastLeft) {
        this.to = to;
        this.cost = cost;
        this.dispatch = repeat;
        this.fastLeft = fastLeft;
    }

    public Route(int to, int cost, int fastLeft) {
        this.to = to;
        this.cost = cost;
        this.fastLeft = fastLeft;
    }

    @Override
    public int compareTo(Route o) {
        return cost - o.cost;
    }
}