[백준]#13905 세부

문제

빼빼로 데이를 맞아 혜빈이와 숭이는 세부에 있는 섬에 놀러 갔다. 섬은 바다 위에 떠다니는 집과 집들을 연결하는 오크나무로 되어있는 다리로 이뤄져 있다. 숭이는 혜빈이에게 깜짝 이벤트를 해주기 위해 섬 관리자에게 혜빈이를 이벤트장소에 머물게 해달라고 하였다. 이벤트 당일 날 숭이는 금으로 된 빼빼로들을 들고 이벤트 장소로 이동하려 했다. 하지만 아뿔싸! 각 다리마다 다리 위를 지날 수 있는 무게 제한이 존재했다. 비싼 금빼빼로를 가면서 버리기 아깝던 숭이는 자신이 머물던 집에서 자신이 혜빈이에게 갈 수 있는 최대한의 금빼빼로만을 들고 가려고 한다. 따라서 숭이는 인공위성조차 해킹할 수 있는 당신에게 혜빈이에게 들고 갈 수 있는 최대한의 금빼빼로 개수를 알려달라고 부탁했다. 당신은 인공위성을 해킹하여 집들의 번호와 다리의 무게제한을 알아내었다. 이 정보를 가지고 빨리 숭이를 도와주자.

(금빼빼로 하나의 무게는 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;
        }
    }
}