boj 1939: 중량제한

start -> end까지 지나는 다리 각각의 최솟값에 대한 최댓값을 구하는 문제이다.

이분탐색으로 중량을 정해두고 BFS로 다리를 지나갈 수 있는지 확인하면 쉽게 풀리는 문제이다.

 

이렇게 풀 경우 서로 같은 두 도시 사이에 여러 개의 다리가 있다는 조건을 딱히 생각해 줄 필요가 없다.

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		LinkedList<Bridge> bridges[] = new LinkedList[v + 1];
		for (int i = 1; i <= v; i++) {
			bridges[i] = new LinkedList<Bridge>();
		}

		int max = 0;
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int size = in.nextInt();

			max = Math.max(max, size);

			bridges[start].add(new Bridge(end, size));
			bridges[end].add(new Bridge(start, size));
		}

		int start = in.nextInt();
		int end = in.nextInt();

		System.out.println(findMinimumWeight(start, end, bridges, max));
	}

	public static int findMinimumWeight(int from, int to, LinkedList<Bridge> bridges[], int end) {
		boolean[] isVisited = new boolean[bridges.length];

		int start = 0;
		int max = 0;

		while (start <= end) {
			int mid = (start + end) / 2;

			if (BFS(from, to, bridges, mid, isVisited)) { // 가능하니까 일단 결과 저장 후 중량을 더 늘려보자
				max = Math.max(max, mid);
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		return max;
	}

	public static boolean BFS(int start, int end, LinkedList<Bridge> bridges[], int maxSize, boolean[] isVisited) {
		clearVisit(isVisited);

		Queue<Integer> queue = new LinkedList<Integer>();

		queue.add(start);
		isVisited[start] = true;

		while (!queue.isEmpty()) {
			int now = queue.poll();

			if (now == end) {
				return true;
			}

			for (Bridge bridge : bridges[now]) {
				if (!isVisited[bridge.destination] && maxSize <= bridge.size) {
					queue.add(bridge.destination);
					isVisited[bridge.destination] = true;
				}
			}
		}

		return false;
	}

	public static void clearVisit(boolean[] isVisited) {
		Arrays.fill(isVisited, false);
	}
}

class Bridge {
	int destination;
	int size;

	public Bridge(int destination, int size) {
		this.destination = destination;
		this.size = size;
	}

	@Override
	public boolean equals(Object o) {
		Bridge bridge = (Bridge) o;
		return destination == bridge.destination;
	}

	@Override
	public int hashCode() {
		return Objects.hash(destination);
	}
}