[BaekJoon] 1939 중량제한 (Java)

1.  문제 링크

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

2.  문제

요약

• N개의 섬으로 이루어진 나라의 몇 개의 섬 사이에는 다리가 설치되어 있어 차들이 다닐 수 있습니다.
• 영식 중공업은 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하는데 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 하는 일이 생깁니다.
• 각 다리마다 중량제한이 있어 중량제한을 초과하는 양의 물품이 다리를 지나면 다리가 무너집니다.
• 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 10,000보다 작거나 같은 N, 1보다 크거나 같고 100,000보다 작거나 같은 M이 주어지고 두 번째 줄부터 M개의 줄에 다리에 대한 정보를 나타내는 세 정수 A, B, C가 주어집니다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미입니다. 마지막 줄에는 공장이 위치해있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어집니다.
  • 1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000,000,000
  • 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있고, 모든 다리는 양방향입니다.
  • 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어집니다.
• 출력: 첫 번째 줄에 답을 출력합니다.

3.  소스코드

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

public class Main {
    static int N, M, company1, company2;
    static HashMap<Integer, ArrayList<Edge>> bridges;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        M = scanner.nextInt();
        bridges = new HashMap<>();
        for(int island = 1; island <= N; island++) bridges.put(island, new ArrayList<>());
        for(int bridge = 0; bridge < M; bridge++) {
            int A = scanner.nextInt(), B = scanner.nextInt(), weight = scanner.nextInt();
            bridges.get(A).add(new Edge(B, weight));
            bridges.get(B).add(new Edge(A, weight));
        }
        company1 = scanner.nextInt();
        company2 = scanner.nextInt();
    }

    static void solution() {
        int max = findMax(company1, company2);
        System.out.println(max);
    }

    static int findMax(int start, int end) {
        int low = 1, high = 1000000000;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];
        int max = Integer.MIN_VALUE;
        while(low <= high) {
            int mid = (low + high) / 2;
            queue.offer(start);
            visited[start] = true;
            if(bfs(queue, mid, end, visited)) {
                max = Math.max(max, mid);
                low = mid + 1;
            } else {
                high = mid - 1;
            }
            queue.clear();
            Arrays.fill(visited, false);
        }
        return max;
    }

    static boolean bfs(Queue<Integer> queue, int mid, int end, boolean[] visited) {
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            for(Edge e : bridges.get(cur)) {
                int city = e.city, weight = e.weight;
                if(weight >= mid) {
                    if(cur == end) return true;
                    if(!visited[city]) {
                        visited[city] = true;
                        queue.offer(city);
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Edge {
        int city, weight;
        public Edge(int city, int weight) {
            this.city = city;
            this.weight = weight;
        }
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch(IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 한 번의 이동에서 옮길 수 있는 물품들의 중량을 이분 탐색을 이용하여 구합니다.
• 문제에서 다리의 중량 제한이 1 이상, 1,000,000,000 이하라고 하였으니 최솟값은 1, 최댓값을 1,000,000,000으로 놓고 이분 탐색을 이용해 공장이 지어진 두 섬 중 한 곳에서 다른 곳으로 이동할 때 거치는 다리들이 해당 중량 이상을 가지는지 판단하여 최대 중량을 구합니다.
  • 공장이 지어진 두 섬 사이에 경로는 BFS를 이용하여 구합니다.
  • 둘 중 한 섬을 시작 지점으로 놓고 만약 아직 탐색하는 지점을 방문하지 않았고 탐색하는 지점으로 이동 시에 이용하는 다리가 이분 탐색에서 정한 중량 이상을 버틸 수 있다면 탐색하는 지점을 Queue에 넣고 다음 탐색 시에 사용합니다.
  • Queue가 비워질 때까지 탐색을 진행하는데 만약 도착 지점에 방문한다면 현재 중량으로 도착 지점으로 이동할 수 있다는 뜻이므로 true를 반환하고 Queue가 비워질 때까지 도착 지점에 도착하지 못한다면 해당 중량으로는 이동할 수 없다는 뜻이므로 false를 반환합니다.
• 만약 현재 중량으로 BFS를 진행했을 때, 이동이 가능했다면 최솟값을 중간값 + 1로 갱신하고 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 갱신합니다.
• 만약 이동할 수 없다면 최댓값을 중간값 - 1로 갱신하여 이동할 수 있는지 확인합니다.
• 위 과정을 반복하여 최솟값이 최댓값을 넘는 경우 그 때까지 갱신된 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값이 이 문제의 답이 됩니다.