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

문제 출처: https://www.acmicpc.net/problem/4386

문제

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

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

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

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

/**
 * kruskal algorithm
 */

public class Main {

    private static int[] parents;

    private static float[][] point;

    private static PriorityQueue<Edge> pq = new PriorityQueue<>();

    private static class Edge implements Comparable<Edge> {

        int from;
        int to;
        float weight;

        public Edge(int from, int to, float weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

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

    private static void makeSet(int n) {
        parents = new int[n];

        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
    }

    private static boolean unionSet(int a, int b) {
        int parentA = findSet(a);
        int parentB = findSet(b);

        if (parentA == parentB) return false;

        parents[parentB] = parentA;

        return true;
    }

    private static int findSet(int a) {
        if (a == parents[a]) return a;

        return parents[a] = findSet(parents[a]); // Path Compression
    }

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

        int N = Integer.parseInt(reader.readLine()); // 별의 개수
        point = new float[N][2];

        for (int i = 0; i < N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            float a = Float.parseFloat(tokenizer.nextToken());
            float b = Float.parseFloat(tokenizer.nextToken());
            point[i][0] = a;
            point[i][1] = b;
        }

        combination(N, 0, 0, new int[2]);

        makeSet(N);

        int cnt = 0;
        float result = 0.f;

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();

            if (unionSet(edge.from, edge.to)) {
                result += edge.weight;
                if (++cnt == N - 1) break;
            }
        }

        System.out.printf("%.2f", result);
    }

    private static void combination(int size, int curr, int cnt, int[] target) {
        if (cnt == 2) {
            // 2개를 뽑았을 때
            pq.offer(new Edge(target[0], target[1], calcDist(target[0], target[1])));
            return;
        }

        for (int i = curr; i < size; i++) {
            target[cnt] = i;
            combination(size, i + 1, cnt + 1, target);
        }
    }

    private static float calcDist(int a, int b) {
        float distX = point[a][1] - point[b][1];
        float distY = point[a][0] - point[b][0];

        return (float) Math.sqrt(Math.pow(distX, 2) + Math.pow(distY, 2));
    }

}

• 크루스칼 알고리즘을 이용하여 풀었다.
• 각 점들의 좌표가 주어지므로 각 점들에 번호를 붙이고 조합을 통해 2개씩 뽑은 뒤 두 점 사이의 관계를 나타내는 간선 클래스를 만들어서 진행하였다.
• 우선순위 큐에 넣음으로써 자동 정렬되는 값들을 하나씩 꺼내어 MST를 완성하였다.