[백준]#4386 별자리 만들기

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

예제 입력 1

3
1.0 1.0
2.0 2.0
2.0 4.0

예제 출력 1

3.41

풀이

이 문제는 MST 알고리즘 중 크루스칼 알고리즘을 이용해서 풀 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    static int[] parent;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Pair[] star = new Pair[N];
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        double ans = 0;
        parent = new int[N];
        for(int i=0; i<N; i++)
            parent[i] = i;

        for(int i=0; i<N; i++) {
            String[] input = br.readLine().split(" ");
            star[i] = new Pair(Double.parseDouble(input[0]), Double.parseDouble(input[1]), 0);
        }

        for(int i=0; i<N-1; i++) {
            Pair x = star[i];
            for(int j=i+1; j<N; j++) {
                Pair y = star[j];

                pq.add(new Pair(i, j, Math.sqrt(Math.pow(x.x-y.x, 2)+Math.pow(x.y-y.y, 2))));
            }
        }

        while(!pq.isEmpty()) {
            Pair temp = pq.poll();
            int x = (int)temp.x;
            int y = (int)temp.y;

            int a = find(x);
            int b = find(y);
            if(a==b) continue;

            union(x, y);
            ans += temp.d;
        }

        System.out.println(String.format("%.2f", ans));
    }

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if(x<y)
            parent[y] = x;
        else
            parent[x] = y;
    }

    public static int find(int x) {
        if(parent[x]==x)
            return x;

        return find(parent[x]);
    }

    public static class Pair implements Comparable<Pair>{
        double x;
        double y;
        double d;

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

        public int compareTo(Pair p) {
            return this.d > p.d ? 1 : -1;
        }
    }
}