문제
N개의 섬과 M개의 다리로 이루어진 무방향 그래프가 있다. 각 다리마다 중량 제한이 있어 해당 값 이하의 물건만 운반할 수 있다. 두 공장 A와 B 사이에서 한 번에 운반할 수 있는 물건의 최대 중량을 구한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 100,000)
다음 M개의 줄에 다리의 양 끝 섬 번호 A, B와 중량 제한 C가 주어진다.
마지막 줄에 두 공장의 섬 번호가 주어진다.
출력
한 번에 운반할 수 있는 물건의 최대 중량을 출력한다.
예제
입력
3 3
1 2 2
3 1 3
2 3 2
1 3출력
3풀이
핵심 아이디어: 운반 가능한 최대 중량 mid를 이분 탐색으로 결정하고, 각 mid에 대해 중량 제한이 mid 이상인 다리만 사용했을 때 A에서 B로 경로가 존재하는지 BFS로 확인한다.
- 이분 탐색 범위:
low = 1,high = maxC(입력된 다리 중량의 최댓값)로 초기화한다. - 중간값 검사:
mid = (low + high) / 2로 기준 중량을 정한다. - BFS 경로 확인: A를 시작점으로 BFS를 실행하되, 현재 노드의 인접 다리 중
w >= mid인 경우만 탐색한다. B에 도달하면 경로 존재로 판단한다. - 탐색 범위 조정:
- 경로가 존재하면:
maxWeight = mid,low = mid + 1(더 큰 값도 가능한지 확인) - 경로가 없으면:
high = mid - 1(기준 중량을 낮춰야 함)
- 경로가 존재하면:
- 결과 출력: 최종
maxWeight가 정답이다.
이분 탐색 + BFS의 조합으로 O(M log C) 시간에 해결할 수 있다. 중량 조건이 단조성을 가지므로(mid가 작을수록 경로가 존재할 가능성이 높음) 이분 탐색 적용이 유효하다.
코드
package day349;
import java.io.*;
import java.util.*;
public class Day342BOJ1939중량제한 {
static class Node {
int end;
int w;
public Node(int end, int w) {
this.end = end;
this.w = w;
}
}
static int N, maxC, maxWeight = 0;
static ArrayList<Node>[] adjList;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
adjList = new ArrayList[N];
for (int i = 0; i < N; i++) {
adjList[i] = new ArrayList<Node>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken()) - 1;
int B = Integer.parseInt(st.nextToken()) - 1;
int C = Integer.parseInt(st.nextToken());
adjList[A].add(new Node(B, C));
adjList[B].add(new Node(A, C));
maxC = Math.max(C, maxC);
}
st = new StringTokenizer(br.readLine());
int factoryA = Integer.parseInt(st.nextToken()) - 1;
int factoryB = Integer.parseInt(st.nextToken()) - 1;
findMaxWeight(factoryA, factoryB);
System.out.println(maxWeight);
}
private static void findMaxWeight(int factoryA, int factoryB) {
int low = 1;
int high = maxC;
Queue<Integer> q = new LinkedList<Integer>();
boolean[] checked = new boolean[N];
while (low <= high) {
int mid = (low + high) / 2;
q.add(factoryA);
checked[factoryA] = true;
boolean existed = existPossibleRoute(q, checked, mid, factoryB);
if (existed) {
maxWeight = Math.max(maxWeight, mid);
low = mid + 1;
} else {
high = mid - 1;
}
q.clear();
Arrays.fill(checked, false);
}
}
private static boolean existPossibleRoute(Queue<Integer> q, boolean[] checked, int mid, int end) {
while (!q.isEmpty()) {
int from = q.poll();
for (Node v : adjList[from]) {
if (v.w >= mid) {
if (from == end) {
return true;
}
if (!checked[v.end]) {
checked[v.end] = true;
q.add(v.end);
}
}
}
}
return false;
}
}복잡도
- 시간: O((V + E) log C) — 이분 탐색 log C번 × BFS O(V+E)
- 공간: O(V + E) — 인접 리스트 및 방문 배열