[백준] 4386 별자리 만들기

문제 링크 : https://www.acmicpc.net/problem/4386

 

🍊해결방법

• 모든 정점을 하나의 선으로 연결했을 때 최소의 비용 구하기
• 크루스칼 사용하자
• 비용은 거리제곱 공식 사용하자

😀풀이

import java.util.*;
import java.io.*;

public class Main {


    static int N;
    static List<double[]> v;
    static int[] parent;
    static PriorityQueue<double[]> pq;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 정점을 하나로 연결 했을 때 최소여야 함
        // 크루스칼 활용

        N = Integer.parseInt(br.readLine());

        v = new ArrayList<>();

        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());

            v.add(new double[]{x, y});
        }


        parent = new int[N];

        for(int i=0; i<N; i++){
            parent[i] = i;
        }

        pq = new PriorityQueue<>((o1, o2) -> Double.compare(o1[2], o2[2]));

        for(int i=0; i<v.size()-1; i++){
            double[] tmp1 = v.get(i);
            for(int j=i+1; j<v.size(); j++){

                double[] tmp2 = v.get(j);

                double w = Math.sqrt(Math.pow((tmp2[0] - tmp1[0]), 2) + Math.pow((tmp2[1] - tmp1[1]), 2));

                pq.add(new double[]{i, j, w});

            }
        }

        double sum = 0;
        while(!pq.isEmpty()){

            double[] tmp = pq.poll();

            int start = (int) tmp[0];
            int end = (int) tmp[1];

            if (find(start) == find(end)) continue;


            union(start, end);

            sum += tmp[2];

        }


        System.out.println(sum);


    } // end main


    static int find(int x){

        if (parent[x] == x)
            return x;

        else{

            parent[x] = find(parent[x]);

            return parent[x];

        }

    }

    static void union(int a, int b){

        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;


    }


}