[백준] 4386번 - 별자리 만들기 (Gold 4)

문제 링크

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

문제 설명

2차원 평면에 n($\leq$ 100)개의 점들이 있다.
n개의 점들을 모두 이으려고 할 때, 이어진 선분의 길이의 합의 최솟값을 구하시오.

정답 코드 및 설명

n개의 점들을 각각 하나의 노드로 보고, 각 노드를 잇는 간선의 가중치가 두 점 사이의 거리인 그래프를 생각하자.
이 그래프의 최소 신장 트리의 총 비용을 구하면 정답을 구한 것이다.

원 그래프는 모든 간선이 서로 연결된 완전 그래프이므로, 간선의 밀도가 매우 높다.
따라서 크루스칼 알고리즘보다는 프림 알고리즘을 사용하는 쪽이 보다 적절하다.
물론, 이 문제의 n은 매우 작기 때문에 크루스칼 알고리즘을 사용해도 문제는 없다.

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

public class BOJ4386 {
    int n;
    double[][] points;
    double[][] dist;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        points = new double[n][2];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            points[i][0] = Double.parseDouble(st.nextToken());
            points[i][1] = Double.parseDouble(st.nextToken());
        }
    }

    void setDist() {
        dist = new double[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = dist(points[i], points[j]);
            }
        }
    }

    double Prim() {
        final double INF = 1_000_000;
        class Star {
            final int starNo;
            final double cost;

            Star(int starNo, double cost) {
                this.starNo = starNo;
                this.cost = cost;
            }
        }
        double totalCost = 0;
        double[] cost = new double[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(cost, INF);
        PriorityQueue<Star> stars = new PriorityQueue<>(Comparator.comparingDouble(s -> s.cost));
        stars.add(new Star(0, 0));
        while (!stars.isEmpty()) {
            Star currStar = stars.poll();
            int curr = currStar.starNo;
            if (visited[curr]) continue;
            totalCost += currStar.cost;
            visited[curr] = true;
            for (int i = 0; i < n; i++) {
                if (dist[i][curr] < cost[i]) {
                    cost[i] = dist[i][curr];
                    stars.add(new Star(i, cost[i]));
                }
            }
        }
        return totalCost;
    }

    double dist(double[] point1, double[] point2) {
        return Math.sqrt((point1[0] - point2[0]) * (point1[0] - point2[0])
                + (point1[1] - point2[1]) * (point1[1] - point2[1]));
    }

    void solution() throws IOException {
        input();
        setDist();
        System.out.println(Prim());
    }

    public static void main(String[] args) throws IOException {
        new BOJ4386().solution();
    }
}