백준 4386 별자리 만들기

문제

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

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
  
  별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

---

코드

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //N 입력 받기
        int n = Integer.parseInt(br.readLine());

        //별들의 좌표 입력 받기
        double[][] stars=new double[n][2];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            stars[i] = new double[]{Double.parseDouble(st.nextToken()), Double.parseDouble(st.nextToken())};
        }

        //간선 정보 저장할 공간 초기화 및 저장
        double[][] edges=new double[n*(n-1)/2][3];
        int index=0;

        for(int i=0; i<n; i++)
            for(int j=i+1; j<n; j++)
                edges[index++]=new double[]{i, j, calculateDistance(stars[i], stars[j])};

        //부모 배열 초기화
        int[] union=new int[n];
        IntStream.range(0, n).forEach(o->union[o]=o);

        //{노드 A, 노드 B, 거리} 중 거리를 기준으로 하는 최소힙
        PriorityQueue<double[]> pq=new PriorityQueue<>(Comparator.comparingDouble(o->o[2]));
        //간선 전부 넣기
        pq.addAll(List.of(edges));

        //index가 노드의 갯수-1 만큼 되면 스패닝 트리 완성
        double answer=0;
        index=0;
        while(!pq.isEmpty()){
            double[] ptr=pq.poll();

            //싸이클을 형성하면 continue
            if(union[(int) ptr[0]]==union[(int) ptr[1]])
                continue;

            //간선 채택
            answer+=Math.sqrt(ptr[2]);

            //부모 합치기
            int parent=Math.min(union[(int) ptr[0]], union[(int) ptr[1]]);
            int child=Math.max(union[(int) ptr[0]], union[(int) ptr[1]]);
            for(int i=0; i<n; i++)
                if(union[i]==child)
                    union[i]=parent;

            if(index==n-1)
                break;
        }

        bw.write(answer+"\n");
        bw.flush();
    }

    //거리 계산
    public static double calculateDistance(double[] a, double[] b){
        return Math.pow((a[0]-b[0]), 2)+Math.pow(a[1]-b[1], 2);
    }
}

---

해결 과정

1. 모든 별 사이의 거리를 계산해둔 뒤에 크루스칼 알고리즘을 사용한다.

2. 😁