[백준] 1939 중량제한 - Java

 

 

 

그래프 탐색 알고리즘과 이분 탐색 알고리즘을 함께 사용하는 문제이다.

 

공장을 두 개 입력받으니, 시작 공장과 도착 공장이 정해진다.

시작 공장에서 도착 공장까지 가려면 중간에 다리를 많이 건너야 한다.

 

다리가 버틸 수 있는 최대 무게가 이분 탐색에서의 Right 부분이 되고, Left부분은 0으로 설정된다.

 

 

이제 문제를 바꿔서 생각해보자.

 

시작 공장에서 중량이 x인 물품을 옮길 때 도착 공장까지 옮길 수 있는가?

 

옮길 수 있으면 답을 갱신하고, 옮길 수 없으면 Right 부분을 갱신한다.

 

 

import java.io.*;
import java.util.*;
 
public class Main {

    static int INF = 987654321;
    static int N, M;
    static ArrayList<Edge>[] list;    
    static int L, R;
    static boolean[] visit;

    static int start, fin;    

    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());

        list = new ArrayList[N + 1];
        visit = new boolean[N + 1];

        for(int i=0; i<N+1; i++) list[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());
            
            list[a].add(new Edge(b, c));
            list[b].add(new Edge(a, c));

            R = Math.max(R, c);
        }

        st = new StringTokenizer(br.readLine());

        start = Integer.parseInt(st.nextToken());
        fin = Integer.parseInt(st.nextToken());

        // BinarySearch();

        System.out.println(BinarySearch());

    }

    static int BinarySearch(){

        int ans = -1;

        while(L <= R){
            visit = new boolean[N + 1];

            int mid = (L + R) / 2;
            visit[start] = true;
            
            Queue<Integer> q = new LinkedList<>();
            q.add(start);

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

                for(Edge k : list[cur]){
                    if(visit[k.dest]) continue;
                    if(k.weight < mid) continue;

                    visit[k.dest] = true;
                    q.add(k.dest);
                }
            }
            

            if(visit[fin]){
                L = mid + 1;
                ans = mid;
            }else{
                R = mid - 1;
            }
        }

        return ans;
    }
    
}

class Edge{
    int dest, weight;

    Edge(int a, int b){
        dest = a;
        weight = b;
    }
}

 

그래프 탐색은 bfs와 dfs모두 가능하다.