문제

이해

N개의 공항, M의 총 비용, K의 티켓 수가 주어집니다.

티켓은 출발 공항 u, 도착 공항 v, 비용 c, 소요시간 d로 이루어집니다.

찬민이는 1에서 출발하여 N에 도착해야합니다. 총 비용 이내로 도착해야 할 때 최단시간을 출력하고 도착할 수 없는 경우에는 Poor KCM을 출력하면 됩니다.

접근

문제의 조건은 데이크스트라를 의미합니다. 출발점이 고정되어 있다는 점과 주어진 정보를 보면 알 수 있습니다.

하지만 일반적인 그래프와 달리 비용이라는 가중치가 추가되어 있으며 경로를 설정할 때 총 비용을 넘으면 안됩니다.

저는 문제를 보고 이전에 풀었던 DP 문제인 "앱" 문제와 비슷하다고 생각했습니다.
boj 7579 앱

위 문제에서는 메모리 안에 들어오도록 앱을 비활성화 했어야 했는데 본 문제에서도 비용 안에 들어온다는 조건이 있습니다. 따라서, 본 문제는 DP의 가능성이 있다고 생각했습니다.

일반적인 데이크스트라를 수행하면 최단거리로 가겠지만 비용이 어떻게 되는지 알 수 없습니다. 비용을 기록해야 했기 때문에 최단거리를 저장하는 배열을 2차원으로 나타내면 어떨까 라고 생각했습니다.

이차원 배열의 첫번쨰 인덱스는 비용이 되고 두번째 인덱스는 노드의 번호가 됩니다. 기존의 데이크스트라라면 단순히 거리가 갱신되면 기록했지만 이차원 배열에서는 현재의 비용 합이 총 비용을 넘지 않는지 확인하고 그 비용 합에 해당하는 최단거리가 더 짧은지 확인하고 갱신하도록 설계했습니다.

또한, 갱신할 수 있다면 현재 비용보다 큰 비용으로도 현재 최단거리로 갈 수 있기 때문에 미리 갱신시켜 놓는다면 시간복잡도를 더욱 줄일 수 있습니다.
(우리는 x으로 y최단거리로 갈 수 있다면 x+1, x+2, x+3의 비용으로 갈 수 있습니다.)

하지만, 여기까지 설계하고 코드를 제출해도 시간초과가 발생합니다. 이 부분에 대해서는 찾아본 결과 데이크스트라를 수행하기 전에 그래프의 간선을 정렬해야 했습니다. 그 이유는 위 문제는 비용이라는 조건이 존재하기 때문에 최악의 경우 (비용이 큰 간선부터 배치되어 있는 경우) 시간복잡도가 커질 수 있기 때문입니다.

풀이

private static void dijkstra() {
        for(int i=1;i<=N;i++){
            Collections.sort(graph[i]);
        }

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        minTime[0][1] = 0;

        pq.add(new Edge(1, 0, 0));

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

            if (cur.to == N) {
                return;
            }

            for (Edge next : graph[cur.to]) {
                int time = cur.time + next.time;
                int cost = cur.cost + next.cost;

                if (cost > M) {
                    continue;
                }

                if (minTime[cost][next.to] > time) {
                    for (int j = cost + 1; j <= M; j++) {
                        if (minTime[j][next.to] <= time) {
                            break;
                        }
                        minTime[j][next.to] = time;
                    }
                    minTime[cost][next.to] = time;
                    pq.add(new Edge(next.to, cost, time));
                }
            }
        }
    }

위는 데이크스트라를 수행하는 코드입니다. 일반적인 데이크스트라지만 2차원으로 설계되어 있습니다. 현재의 비용 합도 저장하며 만일 현재의 비용이 총 비용보다 크다면 continue 합니다.

만일, 가능한 비용이며 해당 비용의 최단거리도 갱신이 가능하다면 갱신을 수행합니다. 위에서 언급했듯이 시간복잡도를 줄이기 위해 cost + 1부터 M까지 최단거리를 갱신했습니다. 만일 반복문 도중 더 작은 값이 있다면 이전 과정에서 갱신되기 때문에 break로 종료합니다.

전체 코드

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

public class Main {
    static final int INF = 100_000_000;

    static class Edge implements Comparable<Edge> {
        int to;
        int cost;
        int time;

        public Edge(int to, int cost, int time) {
            this.to = to;
            this.cost = cost;
            this.time = time;
        }

        @Override
        public int compareTo(Edge o) {
            if (this.time == o.time) {
                return this.cost - o.cost;
            }
            return this.time - o.time;
        }
    }

    static StringTokenizer st = null;
    static StringBuilder sb = new StringBuilder();
    static int N, M, K;
    static List<Edge>[] graph;
    static int[][] minTime;

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

        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            graph = new ArrayList[N + 1];
            for (int i = 1; i <= N; i++) {
                graph[i] = new ArrayList<>();
            }
            minTime = new int[M + 1][N + 1];
            for (int i = 1; i <= M; i++) {
                Arrays.fill(minTime[i], INF);
            }

            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());

                graph[u].add(new Edge(v, c, d));
            }

            dijkstra();
            int min = INF;
            for (int i = 1; i <= M; i++) {
                min = Math.min(min, minTime[i][N]);
            }
            sb.append(min == INF ? "Poor KCM" : min).append("\n");
        }
        System.out.println(sb.toString());
    }

    private static void dijkstra() {
        for(int i=1;i<=N;i++){
            Collections.sort(graph[i]);
        }

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        minTime[0][1] = 0;

        pq.add(new Edge(1, 0, 0));

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

            if (cur.to == N) {
                return;
            }

            for (Edge next : graph[cur.to]) {
                int time = cur.time + next.time;
                int cost = cur.cost + next.cost;

                if (cost > M) {
                    continue;
                }

                if (minTime[cost][next.to] > time) {
                    for (int j = cost + 1; j <= M; j++) {
                        if (minTime[j][next.to] <= time) {
                            break;
                        }
                        minTime[j][next.to] = time;
                    }
                    minTime[cost][next.to] = time;
                    pq.add(new Edge(next.to, cost, time));
                }
            }
        }
    }
}

결과

리뷰

최초에 접근은 빠르게 할 수 있었지만 시간복잡도를 줄이는 과정에서 많은 시간이 소요되었습니다. DP와 데이크스트라의 개념이 섞인 문제라 참신했습니다.