[백준 1939] 중량제한(Java)

문제 링크 : https://www.acmicpc.net/problem/1939

이 문제는 이분 탐색과 bfs를 이용하여 풀 수 있습니다.

문제를 푸는 방식은 다음과 같습니다.

1. 0부터 충분히 큰 수 사이의 무게를 선택한다.
2. 해당 무게를 적재한 후 시작점부터 도착점까지 bfs로 탐색한다
3. 만약 탐색 과정 중 다리의 무게가 견디지 못할 경우 max값을 감소시킨다.
4. 도착점까지 도착 가능하면 min값을 증가시키고 현재 무게를 정답으로 등록한다.

가능한 모든 무게를 테스트해야하기 때문에 더 빠르게 탐색하기 위해 이분 탐색을 진행하였으며, 시작점에서 도착점까지의 경로를 설정하는 것이기 때문에 dfs가 아닌 bfs로 탐색합니다.

다음은 코드입니다.

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

class Main{
    static int N,M,start,end;
    static List<Bridge>[] graph;
    static boolean[] check;

    public static void main(String[] args) throws Exception{
        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 List[N+1];
        for(int i=0;i<=N;i++) graph[i] = 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());
            long C = Long.parseLong(st.nextToken());

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

        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        int min = 0;
        int max = Integer.MAX_VALUE;
        int res = 0;
        while(min<=max){
            int mid = (min+max)/2;
            check = new boolean[N+1];

            if(bfs(mid)){
                min = mid+1;
                res = mid;
            }
            else max = mid-1;
        }
        System.out.println(res);
    }

    static boolean bfs(int mid){
        check[start] = true;
        Queue<Bridge> queue = new ArrayDeque<>();
        queue.add(new Bridge(start,0));

        while(!queue.isEmpty()){
            Bridge curr = queue.poll();
            if(curr.node == end) return true;

            List<Bridge> nexts = graph[curr.node];
            for(Bridge next : nexts){
                if(!check[next.node] && next.weight >= mid){
                    check[next.node] = true;
                    queue.add(next);
                }
            }
        }
        return false;
    }

    static class Bridge{
        int node;
        long weight;

        Bridge(int node, long weight){
            this.node = node;
            this.weight = weight;
        }
    }
}