[백준] 1939번 - 중량제한 (Gold 3)

문제 링크

백준 1939번 - 중량제한 (Gold 3)

문제 설명

N개의 섬 사이를 잇는 M개의 다리가 있다.
모든 다리는 양방향이며, 각 다리에는 중량 제한이 걸려있다.
주어진 두 섬 사이를 이동할 수 있는 중량의 최댓값을 구하시오.

정답 코드 및 설명

조건을 만족하는 최댓값을 구하는 형태의 문제이므로, 매개변수탐색을 사용하면 된다.
주어진 중량이 두 섬 사이를 이동할 수 있는지는 유니온파인드를 통해 알아볼 수 있다.
각 다리에 대해 중량 제한이 주어진 중량보다 크다면, 다리의 시작점과 끝점에 해당하는 집합을 합친다.
모든 다리에 대해 이를 반복했을 때 주어진 두 섬이 같은 집합에 속한다면, 이동이 가능한 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1939 {
    int n, m;
    int start, end;
    int[][] bridge;
    int[] set;

    void input() 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());
        bridge = new int[m][3];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            bridge[i][0] = Integer.parseInt(st.nextToken()); // 다리 시작
            bridge[i][1] = Integer.parseInt(st.nextToken()); // 다리 끝
            bridge[i][2] = Integer.parseInt(st.nextToken()); // 중량 제한
        }
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
    }

    int binarySearch() {
        int start = 0;
        int end = Integer.MAX_VALUE;
        while (start + 1 < end) {
            int mid = (start + end) / 2;
            if (isAble(mid)) start = mid;
            else end = mid;
        }
        return start;
    }

    boolean isAble(int w) {
        set = new int[n + 1];
        for (int i = 1; i <= n; i++)
            set[i] = -1;
        for (int i = 0; i < m; i++) {
            if (w <= bridge[i][2]) union(bridge[i][0], bridge[i][1]);
        }
        return findSet(start) == findSet(end);
    }

    void union(int start, int end) {
        int setStart = findSet(start);
        int setEnd = findSet(end);
        if (setStart == setEnd) return;
        if (-set[setStart] < -set[setEnd]) {
            int temp = setStart;
            setStart = setEnd;
            setEnd = temp;
        }
        if (set[setStart] == set[setEnd])
            set[setStart]--;
        set[setEnd] = setStart;
    }

    int findSet(int a) {
        if (set[a] < 0) return a;
        return set[a] = findSet(set[a]);
    }

    void solution() throws IOException {
        input();
        System.out.println(binarySearch());
    }

    public static void main(String[] args) throws IOException {
        new BOJ1939().solution();
    }
}