BOJ 1939 중량제한

문제

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

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

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

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

문제 분석

1. 정보

   • N개의 섬 $(2 \le N \le 10000)$
   • 각 다리마다 중량제한이 있음
   • M개의 다리에 대한 정보$(1 \le M \le 100000)$
     • $A, B (1 \le A, B \le N), C (1 \le C \le 10^9)$
     • A와 B섬 사이의 C의 중량제한이 있다는 의미

2. 목표

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

3. 제약 조건

   • 중량제한을 초과하는 양의 물품은 다리를 지날 수 없음

풀이

1. 알고리즘
   • BFS
     • BFS를 활용해 공장이 있는 두섬을 가는 경로의 중량 제한을 구함
   • 이분탐색
     • 이분탐색을 활용해 중량의 최대값을 구함
       • 현재 중량을 C라고 했을 경우,
         • BFS를 통해 이동 경로의 중량 제한 값을 구함
         • 만약 경로가 가능하다면 C를 증가, 안된다면 C를 감소 시킴

2. 탐색 과정
   • Node Class를 만들어 그래프를 저장
     • 그래프에는 도착 지점, 중량 제한 값을 저장
   • 이분 탐색할 중량 C를 사용해 이분 탐색
     • C는 1 과 $10^9$ 사이의 중간값부터 시작
     • 만약 이동 경로의 중량 제한 값이 C보다 크다면 C를 증가
     • 작다면 C를 감소
     • left, right 값이 같아질 때까지 반복

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ1939 {

    static class Node{
        int e;
        int w;

        public Node(int e, int w) {
            this.e = e;
            this.w = w;
        }
    }

    static int N, M, S, E;
    static ArrayList<Node>[] list;

    private static void solution() 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());
        list = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list[s].add(new Node(e, w));
            list[e].add(new Node(s, w));
        }
        st = new StringTokenizer(br.readLine());

        S = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        System.out.println(binarySearch());
    }

    static int binarySearch() {
        int low = 1;
        int high = 1_000_000_000;
        int result = 0;
        while(low <= high) {
            int mid = (low + high) / 2;

            if (bfs(mid)) {
                result = mid;
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return result;
    }

    static boolean bfs(int weight) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];
        q.add(S);
        visited[S] = true;
        while(!q.isEmpty()) {
            int cur = q.poll();

            if (cur == E) {
                return true;
            }
            for (Node node : list[cur]) {
                if (!visited[node.e] && node.w >= weight) {
                    visited[node.e] = true;
                    q.add(node.e);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BOJ1939.solution();
    }
}