문제
빼빼로 데이를 맞아 혜빈이와 숭이는 세부에 있는 섬에 놀러 갔다. 섬은 바다 위에 떠다니는 집과 집들을 연결하는 오크나무로 되어있는 다리로 이뤄져 있다. 숭이는 혜빈이에게 깜짝 이벤트를 해주기 위해 섬 관리자에게 혜빈이를 이벤트장소에 머물게 해달라고 하였다. 이벤트 당일 날 숭이는 금으로 된 빼빼로들을 들고 이벤트 장소로 이동하려 했다. 하지만 아뿔싸! 각 다리마다 다리 위를 지날 수 있는 무게 제한이 존재했다. 비싼 금빼빼로를 가면서 버리기 아깝던 숭이는 자신이 머물던 집에서 자신이 혜빈이에게 갈 수 있는 최대한의 금빼빼로만을 들고 가려고 한다. 따라서 숭이는 인공위성조차 해킹할 수 있는 당신에게 혜빈이에게 들고 갈 수 있는 최대한의 금빼빼로 개수를 알려달라고 부탁했다. 당신은 인공위성을 해킹하여 집들의 번호와 다리의 무게제한을 알아내었다. 이 정보를 가지고 빨리 숭이를 도와주자.
(금빼빼로 하나의 무게는 1이고, 숭이의 몸무게는 고려하지 않는다.)
입력
첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄에는 다리의 정보가 주어진다. 각 줄은 “집의 번호 h1(1≤h1≤N), 집의 번호 h2(1≤h2≤N), 다리의 무게제한 k(1≤k≤1,000,000)” 형식으로 주어진다. (h1집과 h2집은 무게제한이 k인 다리로 연결되어 있다.)
출력
숭이의 출발위치에서 혜빈이의 위치까지 숭이가 들고 갈 수 있는 금빼빼로의 최대 개수를 출력하시오.
예제 입력 1
7 9
1 5
1 2 2
1 7 4
2 3 5
3 7 5
4 6 1
6 7 4
5 6 3
5 7 1
3 5 2
예제 출력 1
3
힌트
1-(4)->7-(4)->6-(3)->3
min(4, 4, 3) = 3
풀이
이 문제는 BFS 알고리즘과 BinarySearch 알고리즘을 모두 써서 풀었던 문제이다. 이 문제에서 지역간 관계를 구할 때 관계의 수가 V^2 보다 작을 때, 인접행렬보다 인접리스트는 써야한다는 걸 알아야한다.
또한, 최소한의 BFS 알고리즘을 돌기 위해서 미리 cost를 정한 뒤 BFS 알고리즘을 돌리면 되는 데 이때 cost를 정할 때 이분탐색 알고리즘을 사용해야 한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N;
static ArrayList<Pair>[] map;
static int s;
static int e;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
int M = Integer.parseInt(input[1]);
map = new ArrayList[N+1];
for(int i=1; i<=N; i++)
map[i] = new ArrayList<>();
input = br.readLine().split(" ");
s = Integer.parseInt(input[0]);
e = Integer.parseInt(input[1]);
int high = -1;
int low = 1000001;
int ans = 0;
for(int i=0; i<M; i++) {
input = br.readLine().split(" ");
int start = Integer.parseInt(input[0]);
int end = Integer.parseInt(input[1]);
int cost = Integer.parseInt(input[2]);
map[start].add(new Pair(end, cost));
map[end].add(new Pair(start, cost));
high = Math.max(high, cost);
low = Math.min(low, cost);
}
while(low<=high) {
int mid = (low+high)/2;
if(bfs(mid)) {
ans = mid;
low = mid+1;
}
else
high = mid-1;
}
System.out.println(ans);
}
public static boolean bfs(int cost) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[N+1];
visited[s] = true;
queue.add(s);
while(!queue.isEmpty()) {
int temp = queue.poll();
for(int i=0; i<map[temp].size(); i++) {
int end = map[temp].get(i).end;
int c = map[temp].get(i).cost;
if(!visited[end] && c>=cost) {
if(end==e) return true;
visited[end] = true;
queue.add(end);
}
}
}
return false;
}
public static class Pair {
int end;
int cost;
public Pair(int end, int cost) {
this.end = end;
this.cost = cost;
}
}
}