백준 20182 Java: 이분 탐색과 다익스트라로 최대 수치심 최소화하기

백준 20182번은 시작점에서 도착점까지 가는 비용의 합이 예산을 넘지 않아야 하고, 그중 한 골목에서 내는 최대 비용은 최소여야 하는 문제다. 최대 허용 간선 비용을 하나 정한 뒤, 그 제한 안에서 예산 이하의 경로가 존재하는지 다익스트라로 확인하면 두 조건을 분리할 수 있다.

• 백준 20182번 골목 대장 호석 - 효율성 1

원문에는 사흘 동안 고민한 뒤 페어 프로그래밍하던 동료의 C++ 코드를 해석하며 풀이를 완성한 과정이 남아 있다. 다익스트라라는 방향은 잡았지만 코드로 옮길 때 상태의 의미가 섞였다는 회고도 있었다. 이번에는 그 혼란이 생긴 지점을 반례부터 다시 확인했다.

정점마다 최대 수치심 하나만 저장하면 부족하다

같은 정점에 도착한 두 경로를 생각해 보자.

경로	지금까지 쓴 돈	지금까지의 최대 간선 비용
경로 A	8	4
경로 B	5	5

최대 간선 비용만 보면 A가 낫다. 하지만 남은 간선 비용이 5이고 전체 예산이 10이라면 A는 더 갈 수 없고 B만 도착할 수 있다. 따라서 정점마다 최소 최대 간선 비용 하나만 남기면서 누적 비용을 함께 제한하면, 이후 경로에 필요한 더 싼 상태를 버릴 수 있다.

실제로 1-2(4), 2-4(4), 1-4(5), 4-5(5)이고 예산이 10인 그래프가 이 반례가 된다. 정점 4까지 최대 간선 비용 4인 경로는 총 8이 들지만 도착점까지는 13이 필요하다. 최대 간선 비용 5인 직행 경로는 정점 4까지 총 5가 들고, 도착점까지 정확히 10으로 갈 수 있다.

최대 허용 간선 비용을 결정 문제로 바꾼다

후보 값을 limit이라고 하자. 비용이 limit보다 큰 골목을 모두 제외하고 시작점에서 도착점까지의 최소 누적 비용을 구한다.

• 최소 누적 비용이 예산 이하라면 limit은 가능하다.
• 예산을 넘거나 도착할 수 없다면 limit은 불가능하다.

어떤 limit이 가능하면 그보다 큰 값도 가능하다. 이 단조성을 이용해 입력에 등장한 간선 비용을 정렬하고 이분 탐색한다. 각 후보에서는 음수가 없는 간선의 최소 합을 구해야 하므로 일반 다익스트라를 사용한다.

Java 코드

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

public class Main {
    private static final long INF = Long.MAX_VALUE / 4;

    private static int vertexCount;
    private static int start;
    private static int end;
    private static long budget;
    private static List<Edge>[] graph;

    private static class Edge {
        private final int to;
        private final int cost;

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

    private static class State implements Comparable<State> {
        private final int vertex;
        private final long totalCost;

        private State(int vertex, long totalCost) {
            this.vertex = vertex;
            this.totalCost = totalCost;
        }

        @Override
        public int compareTo(State other) {
            return Long.compare(this.totalCost, other.totalCost);
        }
    }

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

        vertexCount = Integer.parseInt(tokenizer.nextToken());
        int edgeCount = Integer.parseInt(tokenizer.nextToken());
        start = Integer.parseInt(tokenizer.nextToken());
        end = Integer.parseInt(tokenizer.nextToken());
        budget = Long.parseLong(tokenizer.nextToken());

        graph = new ArrayList[vertexCount + 1];
        for (int vertex = 1; vertex <= vertexCount; vertex++) {
            graph[vertex] = new ArrayList<>();
        }

        int[] edgeCosts = new int[edgeCount];
        for (int i = 0; i < edgeCount; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int from = Integer.parseInt(tokenizer.nextToken());
            int to = Integer.parseInt(tokenizer.nextToken());
            int cost = Integer.parseInt(tokenizer.nextToken());

            graph[from].add(new Edge(to, cost));
            graph[to].add(new Edge(from, cost));
            edgeCosts[i] = cost;
        }

        if (start == end) {
            System.out.println(0);
            return;
        }

        Arrays.sort(edgeCosts);
        int left = 0;
        int right = edgeCosts.length - 1;
        int answer = -1;

        while (left <= right) {
            int middle = (left + right) >>> 1;
            int limit = edgeCosts[middle];

            if (canReachWithinBudget(limit)) {
                answer = limit;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        System.out.println(answer);
    }

    private static boolean canReachWithinBudget(int limit) {
        long[] minimumCost = new long[vertexCount + 1];
        Arrays.fill(minimumCost, INF);

        PriorityQueue<State> queue = new PriorityQueue<>();
        minimumCost[start] = 0;
        queue.add(new State(start, 0));

        while (!queue.isEmpty()) {
            State current = queue.poll();

            if (current.totalCost != minimumCost[current.vertex]) {
                continue;
            }
            if (current.totalCost > budget) {
                break;
            }
            if (current.vertex == end) {
                return true;
            }

            for (Edge edge : graph[current.vertex]) {
                if (edge.cost > limit) {
                    continue;
                }

                long nextCost = current.totalCost + edge.cost;
                if (nextCost > budget
                        || nextCost >= minimumCost[edge.to]) {
                    continue;
                }

                minimumCost[edge.to] = nextCost;
                queue.add(new State(edge.to, nextCost));
            }
        }

        return false;
    }
}

왜 이 풀이가 조건을 모두 만족하는가

고정한 limit 아래에서는 허용된 간선만 남는다. 그 그래프에서 다익스트라가 구한 최소 누적 비용이 예산 이하일 때만 가능한 경로라고 판정한다. 이 판정은 누적 비용을 정확히 비교하므로, 앞서 본 두 상태 중 하나를 잘못 버리는 문제가 없다.

가능한 답은 경로 위에 실제로 존재하는 어떤 간선 비용이다. 따라서 모든 정수를 탐색할 필요 없이 정렬한 입력 간선 비용만 후보로 삼을 수 있다. 같은 비용이 여러 번 있어도 정답 값에는 영향을 주지 않는다.

이 글의 다익스트라는 간선 제한을 통과한 그래프에서 누적 비용만 최소화한다. 우선순위 큐와 거리 갱신 자체가 낯설다면 백준 1916 최소비용 구하기 풀이를 먼저 보고, 입력 크기가 더 큰 기본형은 백준 1753 최단경로 풀이와 비교할 수 있다.

간선 수를 M, 정점 수를 N이라 하면 간선 비용 정렬에 O(M log M)이 든다. 다익스트라 한 번은 O((N + M) log N)이고 이를 이분 탐색마다 실행하므로, 전체는 O(M log M + log M × (N + M) log N)이다.

개편 과정에서는 작은 무작위 무방향 그래프의 모든 단순 경로를 열거한 결과와 이분 탐색·다익스트라 결과를 대조했다. Java source는 수동 검토했지만 현재 환경에는 실제 JDK와 BOJ 재제출 결과가 없어 컴파일·채점 통과 여부는 별도 확인이 필요하다.