[BOJ 백준] 11085 - 군사 이동, Java(자바)

문제

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

11085번: 군사 이동

풀이

우선순위 큐에 가중치가 큰 순서로 넣고, 큰 것부터 union-find 연산을 하면서 시작점과 도착점의 대표값이 같은지(연결이 되었는지) 확인 후 연결 되었을 때 빼낸 값 출력(최소값)

코드

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

class Edge implements Comparable<Edge> {
    int from, to, weight;
    
    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge e) {
        return e.weight - this.weight;
    }
}

public class Main {
    static int p, w, start, end;
    static int[] parents;
    static PriorityQueue<Edge> pq;
    
    public static void main(String args[]) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        p = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(in.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        parents = new int[p];
        for (int i = 0; i < p; i++)
            parents[i] = i;
            
        pq = new PriorityQueue<Edge>();
        for (int i = 0; i < w; i++) {
            st = new StringTokenizer(in.readLine());
            pq.offer(new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        
        while(!pq.isEmpty()) {
            Edge temp = pq.poll();
            if (!union(temp.from, temp.to))
                continue;
            if (find(start) == find(end)) {
                System.out.println(temp.weight);
                break;
            }
        }
        
    }
    
    public static boolean union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot == yRoot)
            return false;
            
        parents[yRoot] = xRoot;
        return true;
    }
    
    public static int find(int x) {
        if (x == parents[x])
            return x;
        return parents[x] = find(parents[x]);
    }
}