백준 1939 자바 - 중량제한

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

1939번: 중량제한

문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

코드

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

public class Main {
    private static int n, m, a, b, start, end;
    private static List<Bridge>[] list;
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m  = Integer.parseInt(st.nextToken());

        list = new List[n + 1];
        for (int i = 0; i < n + 1; i++) list[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());
            int c = Integer.parseInt(st.nextToken());
            list[a].add(new Bridge(b, c));
            list[b].add(new Bridge(a, c));
            end = Math.max(end, c);
        }
        st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        while (start <= end) {
            int middle = (start + end) / 2;
            if (bfs(middle)) start = middle + 1;
            else end = middle - 1;
        }
        bw.write(String.valueOf(end));
        bw.flush();
    }

    private static boolean bfs(int limit) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];
        q.offer(a);
        visited[a] = true;

        while(!q.isEmpty()) {
            int front = q.poll();
            if (front == b) return true;

            for (int i = 0; i < list[front].size(); i++) {
                Bridge bridge = list[front].get(i);
                int to = bridge.to;
                int weight = bridge.weight;
                if (visited[to] || weight < limit) continue;
                visited[to] = true;
                q.offer(to);
            }
        }
        return false;
    }

    private static class Bridge {
        int to;
        int weight;

        public Bridge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
}

풀이

 시작값은 0, 끝 값은 입력받은 중량의 최댓값으로 이분 탐색을 돌린다. 끝 점까지 도달할 수 있으면 시작값에 middle + 1을, 아닌 경우 끝 값에 middle - 1 을 넣어준다. 끝 점까지 도달할 수 있는지는 BFS을 통해 구한다.