백준 11085 군사 이동 Java [분리집합 Union find]

https://www.acmicpc.net/problem/11085

11085번: 군사 이동

 

백준 월드에서 큐브 월드를 공격한다는 말은

백준 월드 수도 c와 큐브 월드 수도 v가 하나의 집합에 속해야한다는 뜻이다

경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 최대화하는 경로를 택한다는 말은

큰 길만 골라간 것과 같다

즉, c와 v가 하나의 집합이 될 때까지 너비 기준 최대 우선순위 큐로

입력값을 큐에서 하나씩 꺼내서 서로 연결되지 않았으면 연결한다

c와 v가 하나의 집합에 속하면 최근에 연결한 길의 너비를 출력한다

 

import java.io.*;
import java.util.*;

public class Main {
    static int[] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int P = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
        parents = new int[P];
        for (int p = 0; p < P; p++) parents[p] = p;
        Queue<int[]> queue = new PriorityQueue<>(((o1, o2) -> o2[2] - o1[2]));
        for (int w = 0; w < W; w++) {
            queue.add(Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray());
        }
        int result = 0;
        while (find(c) != find(v)) {
            int[] arr = queue.poll();
            if (find(arr[0]) != find(arr[1])) {
                union(arr[0], arr[1]);
                result = arr[2];
            }
        }
        System.out.println(result);
    }

    static int find(int x) {
        if (parents[x] == x) return x;
        return parents[x] = find(parents[x]);
    }

    static void union(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px != py) parents[px] = py;
    }
}