#백준_1939 중량제한 - Java 자바

# 유형 : 그래프 탐색, 이분 탐색

# 난이도 : 골드 4

# 변수 3개를 갖는 객체타입을 가지는 큐로 BFS구현했는데 시간초과가 나서, 분류를 보니 이분탐색도 포함되어있었다. 어떻게 할지 고민하다가, 답은 입력받는 중량중 하나이기에 입력받은 중량 값 중  가장 낮은 값과 가장 큰 값을 기준으로 이분 탐색을 하며 BFS를 돌리는 방법으로 접근하여 해결하였다.

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p1939 {
    static int N,M;
    static ArrayList<Point> arrList[];
    static boolean visit[];
    static int begin, end;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arrList = new ArrayList[N+1];
        for(int i=0; i<N+1; i++)
            arrList[i] = new ArrayList<>();
        
        int low = 999999, high = 0;
        
        
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            low = Math.min(low, val);
            high = Math.max(high, val);
            arrList[u].add(new Point(v, val));
            arrList[v].add(new Point(u, val));
        }
        st = new StringTokenizer(br.readLine());
        begin = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        
        
        while(low <= high) {
            visit = new boolean[N+1];
            int mid =(low+high)/2;
            if(bfs(mid))
                low = mid+1;
            else
                high = mid-1;
        }
        System.out.println(high);
    }
    private static boolean bfs(int val) {
        // TODO Auto-generated method stub
        Queue<Integer> queue = new LinkedList<Integer>();
        visit[begin] = true;
        queue.add(begin);
        while(!queue.isEmpty()) {
            int poll = queue.poll();
            if(poll == end)
                return true;
            
            for(int i=0; i<arrList[poll].size(); i++) {
                if(!visit[arrList[poll].get(i).x] && val <= arrList[poll].get(i).y) {
                    visit[arrList[poll].get(i).x] = true;
                    queue.add(arrList[poll].get(i).x);
                }
            }
        }
        return false;
    }
    
}