자바 - 백준 1939 / 중량제한

https://www.acmicpc.net/problem/1939

골드3

구현 방법

1. 문제 조건

• N: 섬의 수 (2 ≤ N ≤ 10,000)
• M: 다리의 수 (1 ≤ M ≤ 100,000)
• C: 다리의 최대 중량 (1 ≤ C ≤ 1,000,000,000)
• 두 섬 사이의 여러 경로 중, 한 번의 이동에서 옮길 수 있는 물품들의 최대 중량을 구해야 한다.
• 다리마다 중량 제한이 존재하며, 이를 초과하면 경로로 사용할 수 없다.

2. 완전탐색의 비효율성

• 만약 BFS를 통해 모든 가능한 경로를 탐색하는 방식으로 접근하면:
  • 시간 복잡도는 최악의 경우 O(2^M)에 도달할 수 있다.
  • 이유: 각 다리를 선택하거나 선택하지 않는 경우의 수를 모두 고려해야 하기 때문
  • 이는 M=100,000일 경우 비현실적으로 많은 계산을 요구하기 때문에 적합하지 않다.

3. 매개변수 탐색을 통한 효율적 접근

• 이 문제는 완전탐색 대신 **매개변수 탐색(이진 탐색)**을 통해 해결할 수 있다.
• 핵심 아이디어:
  1. 옮길 수 있는 물품의 중량(최대 중량 제한)을 1∼C 범위로 설정하고, 이 값을 이진 탐색으로 줄여나간다.
  2. 특정 중량 제한에서 BFS 또는 DFS를 사용하여 두 섬을 연결하는 경로가 존재하는지 확인한다.
  3. 중량 제한을 만족하는 경로가 있다면, 더 큰 중량으로 범위를 조정하여 최대값을 탐색한다.
  4. 중량 제한을 만족하지 못한다면, 범위를 줄여가며 탐색을 반복한다.

4. 시간 복잡도 분석

• 이진 탐색: 중량 제한의 범위를 1∼C로 설정하므로 O(logC)의 시간 복잡도를 가짐.
• BFS/DFS 탐색: 한 번의 탐색에서 노드와 간선을 모두 방문하므로 O(N+M)의 시간 복잡도를 가짐.
• 따라서, 전체 시간 복잡도
  • O(logC⋅(N+M))

5. 매개변수 탐색이 적합한 이유

• 매개변수 탐색은 "안 되는 기준"과 "되는 기준"을 명확히 구분할 수 있는 문제에서 효과적으로 사용할 수 있다.
• 이 문제에서는:
  • 특정 중량 제한을 기준으로 BFS/DFS를 통해 경로가 존재하는지 여부를 확인할 수 있다.
  • 경로가 존재하지 않으면 "안 되는 기준", 존재하면 "되는 기준"으로 판단하여 탐색 범위를 좁힐 수 있다.
• 이를 통해 모든 경로를 완전탐색하지 않고도 정답에 도달할 수 있다.

코드

package boj;

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

/**
 * 백준 1939
 * 중량제한
 * 골드3
 * https://www.acmicpc.net/problem/1939
 */
public class Boj1939 {

    private static class Bridge {
        int d;
        int w;

        Bridge(int d, int w) {
            this.d = d;
            this.w = w;
        }
    }

    private static int N; // 섬 개수
    private static int M; // 다리 개수
    private static List<Bridge>[] bridges; // 다리의 최대 중량
    private static int f1; // 공장1
    private static int f2; // 공장2

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        bridges = new List[N + 1];
        for(int i = 1; i <= N; i++)
            bridges[i] = new ArrayList<>();
        int max = 1;
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            bridges[A].add(new Bridge(B, C));
            bridges[B].add(new Bridge(A, C));

            max = Math.max(max, C);
        }

        st = new StringTokenizer(br.readLine());
        f1 = Integer.parseInt(st.nextToken());
        f2 = Integer.parseInt(st.nextToken());

        int start = 1;
        int end = max;
        int result = 1;
        while(start <= end) {
            int mid = (start + end) >>> 1;

            if(bfs(mid)) {
                result = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        System.out.println(result);
    }

    public static boolean bfs(int target) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];

        queue.add(f1);
        visited[f1] = true;

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

            if (current == f2) {
                return true; // f1에서 f2로 이동 가능
            }

            for (Bridge bridge : bridges[current]) {
                if (!visited[bridge.d] && bridge.w >= target) {
                    visited[bridge.d] = true;
                    queue.add(bridge.d);
                }
            }
        }

        return false; // target로는 이동 불가
    }
}