BOJ_4386_별자리 만들기_java

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

4386번: 별자리 만들기

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

/**
 백준 4386번 별자리 만들기
 골드 3
 */
public class BOJ_4386_별자리만들기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine()); // 별의 개수
        double[][] stars = new double[n][2]; // 별의 좌표 정보 배열
        for (int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());
            stars[i][0] = x;
            stars[i][1] = y;
        }
        System.out.println(String.format("%.2f", prim(n, stars)));
    }

    public static double prim(int n, double[][] stars){

        double[][] map = new double[n][n]; // 간선 정보 맵
        for (int i = 0; i<n; i++){
            for (int j = i+1; j<n; j++){
                map[i][j] = calDistance(stars[i][0], stars[i][1], stars[j][0], stars[j][1]);
                map[j][i] = map[i][j];
            }
        }

        boolean[] visited = new boolean[n];
        PriorityQueue<Constellation> queue = new PriorityQueue<>(); // 우선 순위 큐 -> 오름차순
        queue.offer(new Constellation(0, 0));

        int starCnt = 0;
        double distanceSum = 0;
        while (!queue.isEmpty()){
            Constellation star = queue.poll();
            if (visited[star.num]) continue;
            visited[star.num] = true;
            starCnt++;
            distanceSum+= star.distance;
            if (starCnt == n) return distanceSum;
            for (int i = 0; i<n; i++){
                if (!visited[i]) queue.offer(new Constellation(i, map[star.num][i]));
            }
        }
        return -1; // 오류
    }

    public static double calDistance(double x1, double y1, double x2, double y2){
        return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
    }

    public static class Constellation implements Comparable<Constellation>{
        int num;
        double distance;

        public Constellation(int num, double distance){
            this.num = num;
            this.distance = distance;
        }

        @Override
        public int compareTo(Constellation o) {
            return Double.compare(this.distance, o.distance);
        }
    }
}