“[JAVA] 백준 1939번 중량제한 자바 풀이”

in STUDY / PS

사용 알고리즘 : 이분 탐색, BFS, 매개 변수 탐색(Parametric Search)

📚 문제

🔗 문제 링크

백준 1939번: 중량제한

📖 문제 설명

  • N개의 섬으로 이루어진 나라가 있음
  • 몇 개의 섬 사이에는 다리가 설치되어 있어서 물품을 운반할 수 있음
  • 각 다리마다 중량제한이 있음
  • 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구해야 함

🔍 입력 조건

  • 첫째 줄에 N(2 ≤ N ≤ 10,000), M(1 ≤ M ≤ 100,000)이 주어짐
  • 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어짐
  • 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어짐

🔍 출력 조건

  • 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 출력

🧩 문제 분류

  • 알고리즘: 이분 탐색, BFS, 매개 변수 탐색(Parametric Search)
  • 자료구조: 그래프(인접 리스트), 큐
  • 난이도: Gold III

🚀 접근 방법

  1. 그래프를 인접 리스트로 구현하여 섬들의 연결 관계와 중량제한을 저장
  2. 이분 탐색으로 가능한 중량의 범위를 탐색 (1 ~ 최대 중량제한)
  3. BFS를 사용하여 해당 중량으로 시작점에서 도착점까지 이동 가능한지 확인
  4. 이동 가능하면 중량을 늘리고, 불가능하면 중량을 줄임

💻 구현

/**
 * BAEKJOON ONLINE JUDGE
 * 문제 이름 : 중량제한
 * 문제 번호 : 1939
 * 난이도 : GOLD III
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ1939 {
    private static final int MAX_WEIGHT = 1000000000;
    private static final int MAX_N = 10000;
    static int N, M;
    static List<List<Node>> graph;  // 각 섬들마다 연결된 섬들
    static int first, second;   // 연결된 공장 1, 2
    static boolean[] visited;
    
    // 이동할 섬과 그 사이 거리를 Node Class로 설정
    static class Node{
        int v;
        int weight;

        public Node(int v, int weight) {
            this.v = v;
            this.weight = weight;
        }
    }

    // BFS에서 무게를 인자로 받아 공장 간 이동이 가능한지 여부 판단
    public static boolean bfs(int weight){
        Queue<Integer> q = new LinkedList<>();
        visited = new boolean[MAX_N + 1];

        q.offer(first);
        visited[first] = true;

        while (!q.isEmpty()){
            int curr = q.poll();

            if (curr == second) return true;

            for (Node n : graph.get(curr)){
                // 이미 방문했거나 수용가능 무게가 현재 들고있는 무게보다 작다면 패스
                if (visited[n.v] || n.weight < weight) continue;

                q.offer(n.v);
                visited[n.v] = true;
            }
        }

        return false;

    }

    // 이분 탐색 구현 함수
    // "무게"를 기준으로 이분탐색을 진행
    public static int simulate(int s, int e){
        int answer = 0;

        while (s <= e){
            int mid = (s + e) / 2;
            
            // 이동 성공했다면 일단 현재의 최고 무게.
            // 더 큰무게로 이동하여 계속 탐색 진행
            if (bfs(mid)){
                answer = mid;
                s = mid + 1;
            }
            // 이동에 실패했다면 무게를 줄여서 다시 시작
            else e = mid - 1;
        }

        return answer;
    }

    // Main
    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());

        // 그래프 초기화
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++){
            graph.add(new ArrayList<>());
        }

        // 연결 리스트로 섬 간 연결
        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());

            graph.get(A).add(new Node(B, C));
            graph.get(B).add(new Node(A, C));
        }

        // 공장이 위치한 섬 두 가지.
        st = new StringTokenizer(br.readLine());
        first = Integer.parseInt(st.nextToken());
        second = Integer.parseInt(st.nextToken());

        System.out.println(simulate(1, MAX_WEIGHT));
    }
}

⏱ 시간 복잡도

  • O(M log C * (N + M)), 여기서 C는 최대 중량제한
    • 이분 탐색: O(log C)
    • 각 단계에서 BFS: O(N + M)

💾 공간 복잡도

  • O(N + M): 그래프를 저장하는 인접 리스트의 크기

🧪 테스트 케이스

입력출력
3 3
1 2 2
3 1 3
2 3 2
1 3		3

📝 회고

  • 그래프 문제와 이분 탐색이 결합된 형태라 재미있었음.
  • 전혀 못풀던 이분탐색 문제를 어느정도는 알게 된 느낌?
  • 최대값이 1,000,000,000이면 int 범위 내에서 풀이 가능
  • 최대값이 2^32-1 이런 식이면 Long으로 풀어야 함.

📚 참고 자료