[BOJ] 1939 중량제한

✨ Binary Search + BFS/DFS 

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

1939번: 중량제한

---

📍 고려해야할 점

• 두 섬 사이에 여러 개의 다리가 있고 양방향이다. 
• 공장이 있는 두 섬을 연결하는 경로가 반드시 존재한다. (반드시 존재하는 경로의 입력값만 주어짐)
• 옮길 수 있는 물품의 최대 중량 구하기 

 

🕹️ 풀이과정

1️⃣ 입력값으로 주어진 다리 정보 저장 (a섬과 b섬 사이에 중량제한이 c인 다리)

2️⃣ BFS/DFS를 활용해서 섬을 방문하며 최대중량(c)과 비교하면서 다리를 지나갈 수 있는지 파악한다.

3️⃣ 입력된 중량 정보로 최소 중량과 최대 중량을 이용해 Binary Search 하면서 해당 중량((최소+최대)/2)으로 다리를 건널 수 있는지 확인한다.  

 

ex) 

1-2 ➔ 4

1-5 ➔ 2

3-5 ➔ 3

2-3 ➔ 5

3-4 ➔ 1 의 정보를 가지고 있는 섬일 때, 공장이 1번 섬과 5번 섬에 있는 경우 이 경로에서 최대 중량을 찾으면 결과는 3이 된다. 

 

1 👉 2 👉 3 👉 5 경로를 이용할 때 3, 4, 5의 중량으로 건널 수 있고, 

1 👉 5 경로를 이용할 때 2의 중량으로 건널 수 있다. 

첫번째 경로를 이용할 시 3의 중량으로 다리를 건널 수 있으므로(최대중량이 3인 다리를 4 또는 5의 중량으로 건널 수 없음) 최대 중량은 3이 되고, 

두번째 경로를 이용할 시 2의 중량으로 다리를 건널 수 있으므로 최대 중량은 2가 된다. 

 

2와 3을 비교했을 때 결론적으로 최대중량은 3이 되므로 답이 3으로 출력된다. 

 

📍BFS 

static boolean bfs(int weight){
	Queue<Info> queue = new LinkedList<>();
    boolean[] visit = new boolean[N+1]; // N개의 섬
	queue.add(new Info(x, 0)); // x는 공장이 위치해 있는 섬의 번호(시작)
    
    while(!queue.isEmpty()){
    	Info now = queue.poll();
        
        if(now.b==y) return true; // b는 섬의 번호. y는 공장이 위치해 있는 섬의 번호(끝)
        
        for(Info next : queue[now.b]){
        	if(next.c>=weight && !visit[next.b]{
            	queue.add(next);
                visit[next.b] = true;
            }
        }
    }
    return false;
}

 

📍 Binary Search 

static void binarySearch(int l, int r){

    while(l<=r){
    	int mid = (l+r)/2;
        
        if(bfs(mid)){ // mid 중량으로 건널 수 있다면
        	l = mid+1;
            result = mid;
        }else{
        	r = mid-1;
        }
    }
}

 

👩‍💻 전체 코드 - BFS + Binary Search

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

/**
 * Binary Search
 * BFS / DFS
 */
public class BOJ_1939_중량제한 {

    static int N, M;
    static int x,y; // 공장이 위치해 있는 섬의 번호
    static long total;
    static ArrayList<Info>[] arr;

    static class Info{
        int b, c;

        public Info(int b, int c) {
            this.b = b;
            this.c = c;
        }
    }

    static boolean bfs(int weight){
        Queue<Info> queue = new LinkedList<>();
        boolean[] visit = new boolean[N + 1];
        queue.add(new Info(x, 0));

        while (!queue.isEmpty()) {
            Info info = queue.poll();

            if (info.b == y) {
                return true;
            }

            for (Info next : arr[info.b]) {
                if (next.c >= weight && !visit[next.b]) {
                    queue.add(next);
                    visit[next.b] = true;
                }
            }
        }
        return false;
    }

    static void binarySearch(int l, int r) {

        while (l <= r) {
            int mid = (r+l)/2;

            if (bfs(mid)) {
                l = mid + 1;
                total = mid;
            } else {
                r = mid-1;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int left = Integer.MAX_VALUE;
        int right = Integer.MIN_VALUE;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new ArrayList[N+1];

        for (int i = 0; i <= N; i++) {
            arr[i] = 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());

            arr[a].add(new Info(b, c));
            arr[b].add(new Info(a, c));

            left = Math.min(left, c); // 최소 중량
            right = Math.max(right, c); // 최대 중량
        }

        st = new StringTokenizer(br.readLine());
        x = Integer.parseInt(st.nextToken()); // 시작 섬
        y = Integer.parseInt(st.nextToken()); // 도착 섬

        binarySearch(left, right);

        bw.write(String.valueOf(total));
        bw.close();
        br.close();
    }
}