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

---

https://hidelookit.tistory.com/200

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

---

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


public class Main {
	static int N, M;
	static ArrayList<ArrayList<Node>> list = new ArrayList<>();
	static boolean[] visit;
 	public static void main(String arg[]) 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());
 		
 		int left = 0;
 		int right = 0;
 		
 		for(int i = 0; i <= N; i++) {
 			list.add(new ArrayList<>());
 		}
 		
 		int max = 0;
 		
 		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.get(a).add(new Node(b,c));
 			list.get(b).add(new Node(a,c));
 			
 			max = Math.max(max, c);
 		}
 		
 		right = max;
 		st = new StringTokenizer(br.readLine(), " ");
 		int start = Integer.parseInt(st.nextToken());
 		int end = Integer.parseInt(st.nextToken());
 		int result = 0;
 		while(left <= right) { //이분탐색
 			int mid = (left + right) / 2; //무게
 			visit = new boolean[N+1]; //양방향 루프
 			if(bfs(start, end, mid)) {
 				left = mid+1;
 				result = mid;
 			}
 			else {
 				right = mid-1;
 			}
 		}
 		System.out.println(result);
 	}
 	static boolean bfs(int start, int end, int weight) {
 		LinkedList<Integer> queue = new LinkedList<>();
 		queue.add(start);
 		visit[start] = true;
 		while(!queue.isEmpty()) {
 			int s = queue.poll();
 			if(s == end) {
 				return true;
 			}
 			for(Node i : list.get(s)) {
 				if(!visit[i.destination] && weight <= i.cost) {
 					visit[i.destination] = true;
 					queue.add(i.destination);
 				}
 			}
 		}
 		return false;
 	}
	static class Node {
		int destination, cost;
		
		Node (int destination, int cost) {
			this.destination = destination;
			this.cost = cost;
		}
	}
}