[BOJ] 백준 1939번 중량제한 (Java)

#1939 중량제한

난이도 : 골드 4

유형 : 그래프 탐색/ DFS/ 이분 탐색

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인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

▸ 출력

첫째 줄에 답을 출력한다.

 

문제 풀이  

도시와 도시 사이에 연결된 다리로 옮길 수 있는 최대 중량값을 구하면 된다. 특정 지점을 탐색해야 하므로 DFS를 사용할 것이다.

 

📚 조건

• 섬의 갯수 N ( 2 <= N <= 10,000)
• 섬 연결 다리 M ( 1 <= M <= 100,000)
• 시작 다리A, 도착 다리 B, 중량 제한 C  ( 1 <= A,B <= N , 1 <= C <= 1,000,000,000)
• 다리는 양방향, 경로는 항상 존재

 

문제 해결을 하려면 일단 A에서 B로 가는 모든 경로를 조사하여야 한다. 다익스트라와 플로이드-와샬은 그래프 범위가 커서 사용하면 안될 것 같다. 그래서 한 정점에서 다른 특정 정점을 빠르게 탐색하기 위해 DFS탐색을 이용할 것이고 최대 10억까지 운반이 될 수 있는 적절한 중량을 빠르게 찾기 위해 이진탐색을 사용할 것이다.

 

이진탐색은 정렬된 데이터에서만 사용가능한데, 해당 탐색은 0 ~ 최대 중량 Max에서 그래프 탐색이 허용되는 부분을 탐색하는 것이기 때문에 적용이 가능하다.

 

구상

1. 이진탐색을 통해 해당 중량(mid)이 A에서 B로 이동이 가능한지 DFS탐색을 통해 조사한다.
   1. 이동이 가능하면 중량을 늘려서 다시 탐색한다.  left = mid +1;
   2. 이동이 불가능하면 중량을 줄여준 다음 다시 탐색한다. right = mid-1;
2. 탐색이 종료되면 right(최대 중량)을 출력해준다.

 

스케치

pos : 현재 위치한 도시,  target : 도착 도시 B, limit : 무게 제한

limit <= c.w DFS탐색을 통해 제한된 중량을 통과 가능한 경로가 있는지 탐색해준다.

 

static void dfs(int pos, int target, int limit) {
	if(pos == target) {
		ans = pos; 
		return;
	}
	check[pos]= true;
	for(City c : list[pos]) {
		if(!check[c.to] && limit <= c.w ) {
			dfs(c.to, target, limit);
		}
	}
}

 

풀이 코드 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int ans;
	static List<City>[] list;
	static boolean[] check;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		int left =0;
		int right =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 w = Integer.parseInt(st.nextToken());
			
			list[a].add(new City(b,w));
			list[b].add(new City(a,w));
			right = Math.max(right, w); // 그래프 최대 중량 구하기 
		}
		
		st = new StringTokenizer(br.readLine());
		int from = Integer.parseInt(st.nextToken());
		int to = Integer.parseInt(st.nextToken());
		
		while(left<= right) {
			int mid = (left+right)/2;
			ans = -1;
			check = new boolean[n+1];
			dfs(from,to,mid);
			if(ans != -1) { // 이동이 가능하면 중량 올리기
				left = mid+1;
			}else { // 이동 불가능하면 중량 줄이기 
				right = mid-1;
			}
		}
		System.out.println(right);
	}
	
	static void dfs(int pos, int target, int limit) {
		if(pos == target) {
			ans = pos; 
			return;
		}
		check[pos]= true;
		for(City c : list[pos]) {
			if(!check[c.to] && limit <= c.w ) {
				dfs(c.to, target, limit);
			}
		}
	}
}
class City{
	int to;
	int w;
	
	public City(int to, int w) {
		this.to = to;
		this.w = w;
	}
}