[Java] 백준 1939번 : 중량제한

문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

3 3
1 2 2
3 1 3
2 3 2
1 3

예제 출력 1

3

 

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int N, M, A, B;
	private static int max=0;
	private static boolean[] visited;
	private static List<Island>[] list;

	static class Island {
		int num;
		long weight;

		public Island(int num, long weight) {
			super();
			this.num = num;
			this.weight = weight;
		}

		@Override
		public String toString() {
			return "Island [num=" + num + ", weight=" + weight + "]";
		}

	}

	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		list=new ArrayList[N+1];
		for(int i=1;i<=N;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());
			max=Math.max(max, c);
			list[a].add(new Island(b, c));
			list[b].add(new Island(a, c));
		}
		
		st=new StringTokenizer(br.readLine());
		A=Integer.parseInt(st.nextToken());
		B=Integer.parseInt(st.nextToken());
		
		int left=1;
		int right=max;
		while(left<=right) {	// 이분탐색을 통해 가능한 무게를 구함
			int mid=(left+right)/2;
			visited=new boolean[N+1];
			
			if(bfs(mid)) {	// bfs 탐색을 통해 무게가 mid일 때 가능한 경로가 존재하는지 확인
				left=mid+1;	// 가능하면 더 큰 무게 탐색
			} else {
				right=mid-1;	// 불가능하면 더 작은 무게로 설정
			}
		}
		System.out.println(right);
	}

	private static boolean bfs(int mid) {
		Queue<Integer> queue=new LinkedList<>();
		queue.add(A);
		
		boolean []visited=new boolean[N+1];
		visited[A]=true;
		
		while(!queue.isEmpty()) {
			int q=queue.poll();
			
			if(q==B) return true;
			for(Island i:list[q]) {
				if(!visited[i.num] && mid<=i.weight) {	// 아직 방문하지 않았고, 무게가 mid 이상일 때 이동 가능
					visited[i.num]=true;
					queue.add(i.num);
				}
			}
		}
		return false;
	}
}

C의 범위가 10억으로 매우 크기 때문에 시간 초과를 주의해야 합니다.

bfs를 이용할 경우 시간 초과가 발생하고, dfs를 이용할 경우 메모리 초과가 발생하였습니다. 그래서 bfs에 이분 탐색을 통해 시간을 줄여서 해결 가능했던 문제입니다.

bfs + 이분 탐색 을 이용하는 생소하고 까다로운 문제였습니다.