백준 1939 중량제한 (Java)

1. 문제 링크

1939번: 중량제한

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 최대 중량을 넘지 않는 최댓값을 찾아야 한다.

2. 두 섬을 연결시켜야 해서 BFS 탐색을 이용했고, 시간 초과를 생각해 이분 탐색을 함께 이용했다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class Main {
	static class Point {
		int island;
		int weight;
		public Point(int island, int weight) {
			super();
			this.island = island;
			this.weight = weight;
		}
	}
	
	static int N, M, fact, ory, max, min;
	static boolean[] visit;
	static ArrayList<Point>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        String[] split = br.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);
        
        list = new ArrayList[N+1];
        for(int i=0;i<N+1;i++) {
        	list[i] = new ArrayList<>();
        }
        for(int i=0;i<M;i++) {
        	split = br.readLine().split(" ");
        	int a = Integer.parseInt(split[0]);
        	int b = Integer.parseInt(split[1]);
        	int c = Integer.parseInt(split[2]);
        	list[a].add(new Point(b, c));
        	list[b].add(new Point(a, c));
        	
        	max = Math.max(max, c);
        }

        split = br.readLine().split(" ");
        fact = Integer.parseInt(split[0]);
        ory = Integer.parseInt(split[1]);
        
        while(min <= max) {
        	boolean flag = false;
        	
        	int mid = (min + max) / 2;
        	
        	Queue<Integer> queue = new ArrayDeque<>();
        	visit = new boolean[N+1];
        	queue.offer(fact);
        	visit[fact] = true;
        	
        	while(!queue.isEmpty()) {
        		int now = queue.poll();
        		
        		if(now == ory) {
        			flag = true;
        			break;
        		}
        		
        		for(int i=0;i<list[now].size();i++) {
        			Point p = list[now].get(i);
        			if(p.weight >= mid 
        				&& !visit[p.island]) {
        				visit[p.island] = true;
        				queue.offer(p.island);
        			}
        		}
        	}
        	
        	if(flag) {
        		min = mid + 1;
        	}
        	else {
        		max = mid - 1;
        	}
        }
        System.out.println(max);
    }
}