[JAVA]SWEA - 2001 파리 퇴치 (D2)

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

public class Solution {
    static int N;
    static double E;
    static long[][] islands;
    static int[] parent;
    static List<Edge> edges;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());
            islands = new long[N][2];
            edges = new ArrayList<>();

            StringTokenizer tk = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                islands[i][0] = Long.parseLong(tk.nextToken());
            }

            tk = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                islands[i][1] = Long.parseLong(tk.nextToken());
            }

            E = Double.parseDouble(br.readLine());

            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    edges.add(new Edge(i, j, getCost(i, j)));
                }
            }

            double minCost = kruskalMST();
            sb.append("#").append(t).append(" ").append(Math.round(minCost)).append("\n");
        }
        System.out.print(sb);
    }

    static double kruskalMST() {
        Collections.sort(edges);
        parent = new int[N];
        for (int i = 0; i < N; i++) parent[i] = i;

        double totalCost = 0;
        int count = 0;

        for (Edge edge : edges) {
            if (union(edge.u, edge.v)) {
                totalCost += edge.cost;
                if (++count == N - 1) break;
            }
        }
        return totalCost;
    }

    static double getCost(int i, int j) {
        long dx = islands[i][0] - islands[j][0];
        long dy = islands[i][1] - islands[j][1];
        return E * (dx * dx + dy * dy);
    }

    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    static boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return false;
        parent[rootB] = rootA;
        return true;
    }

    static class Edge implements Comparable<Edge> {
        int u, v;
        double cost;

        Edge(int u, int v, double cost) {
            this.u = u;
            this.v = v;
            this.cost = cost;
        }

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

• islands[][] : 각 섬의 (X, Y) 좌표를 저장
• edges : 모든 섬 간의 간선(거리 및 환경 부담금) 저장 리스트
• 간선을 비용 기준 오름차순 정렬
• 각 노드의 부모 노드를 자기 자신으로 설정
• 가장 작은 비용의 간선부터 선택
• 사이클을 방지하기 위해 유니온 파인드 사용
• N-1개의 간선이 선택되면 종료
• totalcost 출력