BOJ1939 중량제한 java

문제

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인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

해설

찾고자하는 값, 즉 최대 중량이 10억이므로 이진 탐색을 떠올려볼만 하다.

N이 최대 10만이라 메모리까지 고려해야 하는 문제다.

처음에는 이중배열과 queue를 이용하여 bfs로 해결하려 했는데 메모리 초과가 났다.

그래서 생각했던 게 Map에 List다.

최대 중량을 가지고 있어야 했고 섬과 섬이 연결된 다리가 여러 개가 존재할 수 있으므로 최대 중량만을 가지는걸로 코드를 구성하였다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int M = Integer.valueOf(st.nextToken());

        List<Map<Integer, Integer>> list = new ArrayList<>();
        for(int i = 0;i<=N;i++) {
            list.add(new HashMap<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.valueOf(st.nextToken());
            int b = Integer.valueOf(st.nextToken());
            int c = Integer.valueOf(st.nextToken());
            int weight = c;

            Integer temp = list.get(a).get(b);
            if(temp != null) {
                if(weight < temp) {
                    weight = temp;
                }
            }
            list.get(a).put(b, weight);
            list.get(b).put(a, weight);
        }

        st = new StringTokenizer(br.readLine());
        int islandA = Integer.valueOf(st.nextToken());
        int islandB = Integer.valueOf(st.nextToken());
        int start, end;
        if (islandA < islandB) {
            start = islandA;
            end = islandB;
        } else {
            start = islandB;
            end = islandA;
        }

        int left = 1;
        int right = 1_000_000_000;
        int result = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (bfs(list, start, end, mid, N)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(result);
    }

    private static boolean bfs(List<Map<Integer,Integer>> list, int start, int end, int mid, int N) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visit = new boolean[N + 1];

        queue.add(start);
        visit[start] = true;
        while (!queue.isEmpty()) {
            int s = queue.poll();
            Map<Integer, Integer> maps = list.get(s);
            for (Map.Entry<Integer, Integer> entry : maps.entrySet()) {
                int next = entry.getKey();
                int weight = entry.getValue();
                if (visit[next]) continue;
                if (weight == 0) continue; // 연결이 안되어 있음
                if (weight < mid) continue; // 최대 중량(mid)보다 무거움
                queue.add(next);
                visit[next] = true;
            }
        }
        return visit[end];
    }
}