[알고리즘] 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인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.
출력
첫째 줄에 답을 출력한다.
접근 방식
N개의 섬이 주어지고 두 섬을 연결하는 양방향 경로를 M개만큼 주고 각 경로의 중량 제한을 준다.
여기서 시작점과 끝점이 주어졌을 때 모든 경로 중 옮길 수 있는 최대 중량을 구하는 것이 문제였다.
Parametric Search 알고리즘을 사용하자
Parametric Search 알고리즘의 주요 포인트는 다음과 같다.
- 최적화 문제(문제의 상황을 만족하는 특정 변수의 최대, 최솟값 구하기) 를 결정 문제로 바꾼다.
- 이분 탐색으로 결정 문제를 해결하며 범위를 좁혀간다.
중량 제한의 문제를 결정 문제로 바꾸면 다음과 같다.
중량 C가 시작점에서 끝점으로 가는 경로를 통과할 수 있나요??이렇게 결정 문제를 바꿨으면 C를 탐색해야 하는데 문제에서 중량 범위는 1 ≤ C ≤ 10억 이다.
이를 이분탐색하는 것은 전혀 복잡하지 않다. (최대 30번)
그렇다면 이제 결정문제를 해결할 차례이다.
결정문제의 해결방법은 다음과 같다.
시작점을 기준으로 bfs 알고리즘으로 탐색
특정 경로의 중량제한이 C 이상일 때만 해당 경로를 탐색해나가서
끝점을 찾으면 통과이고 찾지 못하면 통과히지 못한 것이다.코드
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_1939 {
public static class Node{
int n;
long c;
Node(int n, long c){
this.n = n;
this.c = c;
}
}
static List<List<Node>> edgeList;
static int N, M;
static int start, end;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
edgeList = new ArrayList<>();
for(int i=0;i<=N;i++) {
edgeList.add(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());
long c = Long.parseLong(st.nextToken());
edgeList.get(a).add(new Node(b,c));
edgeList.get(b).add(new Node(a,c));
}
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
long l = 1;
long r = 1000000000L;
long answer = 0;
while(l <= r) {
long mid = (l+r)/2;
if(bfs(mid)) {
answer = mid;
l = mid+1;
}else {
r = mid-1;
}
}
System.out.println(answer);
}
public static boolean bfs(long target) {
Queue<Integer> q = new LinkedList<>();
boolean visited[] = new boolean[N+1];
q.add(start);
visited[start] = true;
while(!q.isEmpty()) {
int node = q.poll();
if(node == end) {
return true;
}
for(Node nextNode : edgeList.get(node)) {
if(!visited[nextNode.n] && target <= nextNode.c) {
visited[nextNode.n] = true;
q.add(nextNode.n);
}
}
}
return false;
}
}