[백준] 10217. KCM Travel

문제 링크

[백준] 10217. KCM Travel

풀이 과정

다익스트라 활용 문제입니다. 일반적인 다익스트라 알고리즘은 최소 비용 경로를 구하는 반면, 이 문제는 제한된 비용(M) 이하이면서 최소 시간을 만족하는 경로를 채택해야 합니다. 따라서, 2차원 배열을 사용해야 했습니다.

문제에서 사용된 2차원 배열 dp 는 다음과 같은 의미를 갖습니다.

dp[i][j] = 1번 공항에서 i번 공항까지 j원의 비용을 들여 도달했을 때의 최소 시간

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

    if(now.vertex == N) {
        answer = now.time;
        break;
    }

    for (Edge next : adj[now.vertex]) {
        if (now.cost + next.cost > M) continue;

        if (dp[next.vertex][now.cost + next.cost] > now.time + next.time) {
            dp[next.vertex][now.cost + next.cost] = now.time + next.time;
            pq.add(new Edge(next.vertex, now.cost + next.cost, dp[next.vertex][now.cost + next.cost]));
        }
    }
}

우선순위 큐를 사용해 다익스트라를 구현했으며, 우선순위 큐는 시간을 기준으로 오름차순 정렬됩니다. 아래는 연결된 정점들에 대해 확인하는 조건들에 대한 설명입니다.

• 연결된 정점에 대한 간선의 비용과 현재까지 든 비용을 더했을 때 그 값이 M을 초과하게 되면, M원 이하를 사용해야 하는 문제의 조건에 어긋나므로 큐에 넣지 않습니다.
• 만약 더 적은 시간으로 연결된 다음 정점까지 갈 수 있다면, dp 배열 요소를 갱신해준 다음, 큐에 새로 넣어줍니다.

코드

import java.util.*;

public class BOJ_10217_KCMTravel {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int TC = sc.nextInt();

        for (int tc = 1; tc <= TC; tc++) {
            int N, M, K;
            N = sc.nextInt();
            M = sc.nextInt();
            K = sc.nextInt();

            ArrayList<Edge>[] adj = new ArrayList[N + 1];
            int[][] dp = new int[N + 1][M + 1];

            for (int i = 1; i <= N; i++) {
                adj[i] = new ArrayList<>();
                Arrays.fill(dp[i], Integer.MAX_VALUE);
            }

            for (int i = 0; i < K; i++) {
                int u, v, c, d;
                u = sc.nextInt();
                v = sc.nextInt();
                c = sc.nextInt();
                d = sc.nextInt();

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

            PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
                @Override
                public int compare(Edge o1, Edge o2) {
                    return o1.time - o2.time;
                }
            });

            dp[1][0] = 0;
            pq.add(new Edge(1, 0, 0));
            int answer = Integer.MAX_VALUE;

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

                if(now.vertex == N) {
                    answer = now.time;
                    break;
                }

                for (Edge next : adj[now.vertex]) {
                    if (now.cost + next.cost > M) continue;

                    if (dp[next.vertex][now.cost + next.cost] > now.time + next.time) {
                        dp[next.vertex][now.cost + next.cost] = now.time + next.time;
                        pq.add(new Edge(next.vertex, now.cost + next.cost, dp[next.vertex][now.cost + next.cost]));
                    }
                }
            }

            System.out.println(answer == Integer.MAX_VALUE ? "Poor KCM" : answer);
        }
    }

    static class Edge {
        int vertex, cost, time;

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