[백준] 4386: 별자리 만들기 JAVA

접근

다른 크루스칼 문제들과 핵심 알고리즘은 동일하고, 그 이외의 전처리할 것들이 추가되어 단순히 구현 난이도만 조금 높아진 문제같다. 

 

코드

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

public class BJ4386 {
    static class Pos{
        double x, y;

        public Pos(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Edge implements Comparable<Edge> {
        int from, to;
        double dist;

        public Edge(int from, int to, double dist) {
            this.from = from;
            this.to = to;
            this.dist = dist;
        }

        @Override
        public int compareTo(Edge o) {
            return (int)(this.dist - o.dist);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int n = Integer.parseInt(br.readLine());
        ArrayList<Pos> stars = new ArrayList<>();

        // 입력값 저장
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());
            stars.add(new Pos(x, y));
        }

        // 별들 간의 거리 계산
        PriorityQueue<Edge> pq = addEdge(stars);

        double answer = kruskal(n, pq);
        System.out.printf("%.2f", answer);
    }

    static double kruskal(int n, PriorityQueue<Edge> pq){
        double res = 0;
        int[] root = new int[n];

        for (int i = 0; i < n; i++)
            root[i] = i;

        int cnt = 0;
        while(!pq.isEmpty()){
            if(cnt == n-1) break;
            Edge e = pq.poll();

            int r1 = find(root, e.from);
            int r2 = find(root, e.to);

            if(r1 == r2) continue;

            union(r1, r2, root);
            res += e.dist;
            cnt++;
        }

        return res;
    }

    static int find(int[] root, int n){
        if(root[n] == n) return n;
        return root[n] = find(root, root[n]);
    }

    static void union(int r1, int r2, int[] root){
        root[r1] = r2;
    }

    private static PriorityQueue<Edge> addEdge(ArrayList<Pos> stars) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int starCnt = stars.size();

        for (int i = 0; i < starCnt; i++) {
            for (int j = i+1; j < starCnt; j++) {
                double dist = calcDist(stars.get(i), stars.get(j));
                pq.add(new Edge(i, j, dist));
            }
        }

        return pq;
    }

    private static double calcDist(Pos p1, Pos p2) {
        return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
    }
}