[백준 / 골드4] 1939번 중량제한 (Java)

문제 보기

이분 탐색 + 브루트 포스 조합을 기억하자.

풀이

• 한 번의 이동에서 옮길 수 있는 물품들의 무게의 최댓값을 효율적으로 구하기 위하여 이분 탐색 사용
• 해당 무게로 출발지에서 목적지까지 도착할 수 있는지 확인하기 위하여 BFS 사용
  
  
• 목적지와 건널 수 있는 무게를 필드값으로 가지고 있는 Bridge 사용
• bridges를 만들고 초기화 시켜줌
• bridges.get(출발지).add(new Bridge(목적지, 무게)) 를 계속 추가해 줌
• 이렇게 구현해야 출발지에서 건널 수 있는 모든 다리의 목적지, 무게를 빠른 시간, 낮은 메모리로 찾을 수 있음
• 0과 모든 다리의 최대 무게를 사이로 이진 탐색 시작
• queue에 현재 섬에서 방문 안했고 건널 수 있는 목적지를 계속 넣어줌
• 현재 섬이 최종 목적지인 경우 true 반환

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] sizes = Arrays.stream(br.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();

        ArrayList<ArrayList<Bridge>> bridges = new ArrayList<>();
        for (int i = 0; i <= sizes[0]; i++) {
            bridges.add(new ArrayList<>());
        }

        int maxWeight = 0;
        for (int i = 0; i < sizes[1]; i++) {
            int[] bridge = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
            bridges.get(bridge[0]).add(new Bridge(bridge[1], bridge[2]));
            bridges.get(bridge[1]).add(new Bridge(bridge[0], bridge[2]));
            if (bridge[2] > maxWeight) {
                maxWeight = bridge[2];
            }
        }

        int[] way = Arrays.stream(br.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();

        int left = 0;
        int right = maxWeight;
        while (left <= right) {
            int mid = (left + right) / 2;

            if (bfs(bridges, way, mid, new boolean[sizes[0] + 1])) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(right);
    }

    public static boolean bfs(
        ArrayList<ArrayList<Bridge>> bridges,
        int[] way,
        int weight,
        boolean[] visited
    ) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(way[0]);
        visited[way[0]] = true;

        while (!queue.isEmpty()) {
            int current = queue.remove();

            if (current == way[1]) {
                return true;
            }

            for (Bridge bridge : bridges.get(current)) {
                if (!visited[bridge.getDestination()] && bridge.getWeight() >= weight) {
                    visited[bridge.getDestination()] = true;
                    queue.add(bridge.getDestination());
                }
            }
        }
        return false;
    }
}

class Bridge {

    private final int destination;
    private final int weight;

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

    public int getDestination() {
        return destination;
    }

    public int getWeight() {
        return weight;
    }
}