백준 4386 별자리 만들기 Java [최소스패닝트리, 프림]

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

4386번: 별자리 만들기

 

최소 스패닝 트리 문제이다

아무 생각없이 프림을 사용해서 풀었는데 풀고보니 크루스칼으로 푸는게 좋아보인다

N x N 행렬을 만들고 피타고라스의 정의 a^2 + b^2 = c^2를 활용해 두 변 사이의 거리를 구해 넣어줬다

우선순위큐에서 거리를 기준으로 최소값을 꺼내 방문 하지 않은 노드들을 방문해가면서 결과값에 더해줬다

출력은 10^-2까지만 구하면 된다

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int cnt = N;
        double result = 0;
        StringTokenizer st;
        double[][] stars = new double[N][2];
        double[][] dist = new double[N][N];
        boolean[] vtd = new boolean[N];
        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            stars[n][0] = Double.parseDouble(st.nextToken());
            stars[n][1] = Double.parseDouble(st.nextToken());
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j) continue;
                double len = Math.sqrt(Math.pow(stars[i][0] - stars[j][0], 2)
                        + Math.pow(stars[i][1] - stars[j][1], 2));
                dist[i][j] = len;
                dist[j][i] = len;
            }
        }
        PriorityQueue<double[]> queue = new PriorityQueue<>((a,b) -> (int) (a[0] - b[0]));
        queue.add(new double[]{0, 0});
        while (!queue.isEmpty() && cnt > 0) {
            double[] now = queue.poll();
            int n = (int) now[1];
            if (vtd[n]) continue;
            vtd[n] = true;
            cnt--;
            result += now[0];
            for (int i = 0; i < N; i++) {
                if (vtd[i]) continue;
                queue.add(new double[]{dist[n][i], i});
            }
        }
        System.out.printf("%.2f", result);
    }
}