백준 4386 - 별자리 만들기

문제

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

리뷰

크루스칼을 이용하여 간단히 풀이할 수 있는 문제였다.

정점간 위치가 좌표로 주어지는 상황에서 MST를 형성해주면 되는 문제였다.
좌표를 표현하기 위해 Point 클래스를 산정하였으며 주어진 모든 좌표간
간선을 설정하여 비용 기준 최소힙에 저장한 후, 크루스칼 로직을 통하여
답을 도출하였다.

로직의 시간복잡도는 설정할 수 있는 간선의 개수가 $n \times n-1$개일 때
크루스칼의 시간복잡도인 $O(nlog(n^2))$으로 수렴하고 이는 $n=100$인
최악의 경우에도 무난히 제한 조건 1초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.parseInt;

public class Main {
    static int N;
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingDouble(e -> e.w));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = parseInt(br.readLine());

        parent = new int[N];

        List<Point> points = new ArrayList<>();
        StringTokenizer st;
        double x, y;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            x = Double.parseDouble(st.nextToken());
            y = Double.parseDouble(st.nextToken());

            points.add(new Point(x, y));
        }

        for (int u = 0; u < points.size() - 1; u++)
            for (int v = u + 1; v < points.size(); v++)
                pq.offer(new Edge(u, v, getDist(points.get(u), points.get(v))));

        System.out.printf("%.2f\n", kruskal());
        br.close();
    }

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


    static double kruskal() {
        Arrays.fill(parent, -1);
        int r1, r2, selected = 0;
        double result = 0;

        while (!pq.isEmpty() && selected < N - 1) {
            Edge e = pq.poll();

            r1 = find(e.u);
            r2 = find(e.v);

            if (r1 == r2) continue;

            if (parent[r1] < parent[r2]) {
                parent[r1] += parent[r2];
                parent[r2] = r1;
            } else {
                parent[r2] += parent[r1];
                parent[r1] = r2;
            }

            selected++;
            result += e.w;
        }

        return result;
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

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

    static class Point {
        double x, y;

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

    static class Edge {
        int u, v;
        double w;

        public Edge(int u, int v, double w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

결과