220815 - 중량제한

◾ 중량제한 : 백준 1963번 (골드 3)

• https://www.acmicpc.net/problem/1963

문제

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

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

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

---

입력

• 첫째 줄 : 섬의 개수 N(2 <= N <= 10000), 다리의 개수 M(1 <= M <= 100000)
• 다음 M줄 : 다리 정보 A, B, C (1 <= A, B <= N / 1 <= C <= 1000000000)
  • A, B에 중량 제한이 C인 다리를 의미.
  • 모든 다리는 양방향.
• 마지막 줄 : 공장의 위치를 나타내는 두 정수(1 <= 정수 <= N).

출력

• 한 번에 옮길 수 있는 중량의 최댓값.

입출력 예

Input	Output
3 3 1 2 2 3 1 3 2 3 2 1 3	3

---

◾ 풀이

1. 해설

• BFS와 이분 탐색을 활용해 해결. (이분 탐색으로 중량의 범위를 좁혀가며 진행.)
  • 기준 중량에 대해 이분 탐색을 진행.
  • 해당 중량으로 옮길 수 있는지 BFS로 확인.
    • 가능하다면 더 큰 범위에서 반복.
    • 불가능하다면 더 작은 범위에서 반복.

---

2. 프로그램

1. 섬의 개수, 다리 개수 입력.
2. 리스트에 다리 정보를 담을 수 있도록 준비.
   • 리스트의 인덱스 : 섬 번호
   • 리스트의 데이터 : 섬에 연결된 다리 정보 리스트.
   • left, right 범위 지정(left 최소 중량, right 최대 중량)
3. 이분 탐색을 통해 기준 중량 선택.
4. BFS를 통해 가능한 중량인지 확인
   • 가능하다면 : 더 큰 범위의 중량 확인. (left 이동), 정답 수정.
   • 불가능하다면 : 더 작은 범위의 중량 확인. (right 이동)

# 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		st = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(st.nextToken());	// 섬의 개수.
		int m = Integer.parseInt(st.nextToken());	// 다리의 개수.

		// 각 섬에 연결된 다리 정보를 담을 자료 구조.
		//   - int[2] => [0] : 연결된 섬, [1] : 최대 중량
		List<ArrayList<int[]>> island = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			island.add(new ArrayList<>());
		}
		// 이분 탐색을 위한 범위.
		int left = Integer.MAX_VALUE;	// 연결된 다리의 최소 중량.
		int right = Integer.MIN_VALUE;	// 연결된 다리의 최대 중량.
		// 다리 정보 입력.
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(in.readLine());
			int A = Integer.parseInt(st.nextToken());	// 섬1
			int B = Integer.parseInt(st.nextToken());	// 섬2
			int C = Integer.parseInt(st.nextToken());	// 최대 중량

			// A, B섬에 대해 모두 다리 정보 추가. (다리가 양방향이기 때문.)
			island.get(A).add(new int[] { B, C });
			island.get(B).add(new int[] { A, C });

			// 최대 중량에 따라 최솟값, 최댓값 변경.
			left = Math.min(left, C);
			right = Math.max(right, C);
		}

		// 공장이 있는 섬의 위치.
		st = new StringTokenizer(in.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
		// 이분 탐색을 통해 각 중량이 가능한지 확인. (가능하다면 정답 변경)
		int answer = 0;
		while (left <= right) {
			// 기준 중량.
			int mid = (right + left) / 2;
			// bfs를 통해 해당 중량이 가능한지 확인.
			// - 가능하다면 : [정답 변경], [left 인덱스 변경]
			// - 불가능하다면 : [right 인덱스 변경]
			if(bfs(island, start, end, mid, n)) {
				answer = mid;
				left = mid + 1;
			}else {
				right = mid - 1;
			}
		}

		sb.append(answer);
		System.out.println(sb);
	}
	
	// BFS를 통해 이동이 가능한지 확인하는 함수.
	// - island : 각 섬에 연결된 다리 정보를 담은 리스트.
	// - start : 시작 섬.
	// - end : 끝 섬.
	// - v : 기준 중량.
	// - n : 섬의 개수.
	public static boolean bfs(List<ArrayList<int[]>> island, int start, int end, int v, int n) {
		// BFS를 통해 탐색.
		// - 첫 요소 start 추가.
		Deque<Integer> queue = new LinkedList<>();
		queue.offerLast(start);
		
		// 방문 표시 배열.
		// - 첫 요소 start 방문 표시.
		boolean[] visited = new boolean[n+1];
		visited[start] = true;
		
		// 덱이 빌 때까지 반복.
		while(!queue.isEmpty()) {
			// 섬의 번호 반환.
			int p = queue.pollFirst();
			
			// p에 연결된 모든 섬 확인.
			for(int[] next : island.get(p)) {
				// 방문하지 않고 기준 중량 이상인 경우만 추가.
				if (!visited[next[0]] && next[1] >= v) {
					// 다음 위치가 end이면 true 반환. 
					if (next[0] == end) {
						return true;
					}
					// 방문 표시, 덱에 추가.
					visited[next[0]] = true;
					queue.offerLast(next[0]);
				}
			}
		}
		
		return false;
	}
}