[Java] 백준 1939번 - 중량제한

[문제]

 

[풀이]

이중탐색 + BFS를 사용하는 문제로 아래의 블로그를 참고하였습니다.

https://hidelookit.tistory.com/200

[백준 1939] 중량제한 (자바)

 

left에 최소값 0을 삽입합니다.

right 에 다리들중 가장 중량이 큰값을 넣어줍니다.

 

(left + right)/2인 mid 값부터 해당 중량의 짐으로 섬-섬을 이동할수 있는지 확인하며,

만약 이동할수 있다면 mid+1, 이동할수없다면 mid-1하며 최대 중량을 찾습니다.

 

[코드]

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;

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

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

public class Main {
    public static int N;
    public static int M;
    public static ArrayList<ArrayList<Bridge>> bridge = new ArrayList<>();
    public static int max = 0;
    public static void main(String[] args) 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());

        for(int i=0;i<=N;i++) {
            bridge.add(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());
            // 양뱡향이라 2개 넣어줌
            bridge.get(a).add(new Bridge(b,c));
            bridge.get(b).add(new Bridge(a,c));

            if(max < c) {
                max = c;
            }
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        int left = 0;
        int right = max;

        while(left <= right) {
            int mid = (left + right)/2;
            if(bfs(start,end,mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
    public static boolean bfs(int start, int end, int mid) {
        boolean[] visit = new boolean[N+1];
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visit[start] = true;

        while(!q.isEmpty()) {
            int p = q.poll();

            if(p == end) {
                return true;
            }

            for(Bridge i: bridge.get(p)) {
                if(!visit[i.island] && mid <= i.weight) {
                    visit[i.island] = true;
                    q.add(i.island);
                }
            }
        }
        return false;
    }
}