[ BOJ ][JAVA][4386] 별자리 만들기

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

4386번: 별자리 만들기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	4632	2505	2009	54.268%

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 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
    모든 간선들을 pq에 추가해주고, union-find를 통해 MST를 만든다.
*/
import java.io.*;
import java.util.*;
public class p4386 {
    static class Edge implements Comparable<Edge> {
        int s, e;
        double cost;
        public Edge(int s, int e, double cost) {
            this.s = s;
            this.e = e;
            this.cost = cost;
        }
        public int compareTo(Edge o) {
            if (cost - o.cost > 0) {
                return 1;
            } else {
                return -1;
            }
        }
    }
    static class Pair {
        int id;
        double x, y;
        public Pair (int id, double x, double y) {
            this.id = id;
            this.x = x;
            this.y = y;
        }
    }
    static int n;
    static int[] parent, rank;
    static Pair[] pair;
    static PriorityQueue<Edge> pq = new PriorityQueue<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
        rank = new int[n + 1];
        pair = new Pair[n + 1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());
            pair[i] = new Pair(i, x, y);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                double x1 = pair[i].x;
                double y1 = pair[i].y;
                double x2 = pair[j].x;
                double y2 = pair[j].y;
                pq.add(new Edge(i, j, calc(x1, y1, x2, y2)));
            }
        }
        mst();
    }

    static void mst() {
        double ret = 0;
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            int u = cur.s;
            int v = cur.e;

            if (find(u) == find(v)) continue;
            union(u, v);

            ret += cur.cost;
        }
        System.out.println(ret);
    }

    static double calc(double x1, double y1, double x2, double y2) {
        double a = x2 - x1;
        double b = y2 - y1;
        return Math.sqrt((a * a) + (b * b));
    }

    static void union(int u, int v) {
        u = find(u);
        v = find(v);
        if (u != v) {
            if (rank[u] < rank[v]) {
                parent[u] = v;
            } else {
                parent[v] = u;
                if (rank[u] == rank[v]) {
                    rank[u]++;
                }
            }
        }
    }

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

        return parent[x] = find(parent[x]);
    }
}