백준 - 4386 별자리 만들기(Java)

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

4386번: 별자리 만들기

 

크루스칼(Kruskal) 문제입니다.

크루스칼은 유니온-파인드(Union-Find)를 이용해서 최소 스패닝 트리를 만드는 문제입니다.

크루스칼은 기본적으로 최소의 간선만을 선택하여 트리를 만들기 때문에, 시작 정점은 존재하지 않습니다.

(시작 정점이 있으면 프림을 사용하면 됩니다.)

 

문제에서 별들의 2차원 에서의 x,y 좌표만 주어지기 때문에 모든 별들의 거리는 직접 구하셔야합니다.

여기서 사용되는 공식은 피타고라스 정리입니다.

a² + b² = c²

 

위 공식을 이용해 모든 별들의 거리를 구해서 저장하고, 거리가 최소인 두 별들을 선택해서 최소 스패닝 트리를 만들어주면 됩니다.

저는 따로 정렬을 하지 않고, 우선순위큐를 사용했습니다.

그리고 별의 개수가 N이라고 하면 최소 스패닝 트리를 만드는 간선은 N-1이기 때문에, 간선이 다 만들어지면 중간에 멈추면 됩니다.

 

[구현 코드]

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

public class Main {
    private static int n;
    private static double[][] stars;
    private static PriorityQueue<Star> pq;
    private static int[] parents;

    private static class Star implements Comparable<Star> {
        int s;
        int e;
        double x1, x2;
        double y1, y2;
        double dis;

        Star(int s, int e, double x1, double x2, double y1, double y2, double dis) {
            this.s = s;
            this.e = e;
            this.x1 = x1;
            this.x2 = x2;
            this.y1 = y1;
            this.y2 = y2;
            this.dis = dis;
        }

        @Override
        public int compareTo(Star o) {
            if(this.dis > o.dis){
                return 1;
            }else if(this.dis < o.dis){
                return -1;
            }else {
                return 0;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        n = Integer.parseInt(br.readLine());
        stars = new double[n + 1][2];
        parents = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            stz = new StringTokenizer(br.readLine(), " ");
            stars[i][0] = Double.parseDouble(stz.nextToken()); // x좌표
            stars[i][1] = Double.parseDouble(stz.nextToken()); // y좌표

            parents[i] = i;
        }

        pq = new PriorityQueue<>();

        for (int i = 1; i < n + 1; i++) {
            for (int j = i + 1; j < n + 1; j++) {
                double x1 = stars[i][0];
                double y1 = stars[i][1];

                double x2 = stars[j][0];
                double y2 = stars[j][1];

                double x = Math.pow(x1 - x2, 2);
                double y = Math.pow(y1 - y2, 2);

                double dis = Math.sqrt(x + y);

                pq.add(new Star(i, j, x1, x2, y1, y2, dis));
            }
        }

        double total = 0.0;
        int cnt = n - 1;
        while (!pq.isEmpty() && cnt > 0) {
            Star star = pq.poll();

            if(union(star.s, star.e)){
                total += star.dis;
                cnt--;
            }
        }

        // 소수 둘 째 자리까지 주어지기 때문에 100을 곱함
        double ans = (double) Math.round(total * 100) / 100;
        bw.write(String.valueOf(ans));

        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean union(int a, int b){
        int root1 = find(a);
        int root2 = find(b);

        if(root1 == root2){
            return false;
        }

        if(root2 > root1){
            parents[root2] = root1;
        }else{
            parents[root1] = root2;
        }

        return true;
    }

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