문제 풀이(8)

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

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



class Node{
	double x;
	double y;
	int index;

	Node(double x , double y, int index)
	{
		this.x = x;
		this.y = y;
		this.index = index;
	}

	@Override
	public String toString()
	{
		return x +" "+ y+" "+index;
	}
}


class Edge implements Comparable  <Edge>{

	int s;
	int e;
	double v;

	Edge(int s , int e , double v)
	{
		this.s = s;
		this.e = e;
		this.v = v;
	}

	@Override
	public int compareTo(Edge oterNode)
	{
		return (int)this.v - (int)oterNode.v;
	}

}

public class Main {

	static PriorityQueue<Edge> pq = new PriorityQueue<>();

	static int[] parent;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = 
        new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		Node[] nodes = new Node[n];

		

		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());
			
			nodes[i] = new Node(x, y,i);
		}
		

		for (int i = 0; i < n; i++) {
			for (int j = i+1; j < n; j++) {
			
			
				Node n1 = nodes[i];

				Node n2 = nodes[j];

				
				double result = distance(n1 , n2 );

				pq.offer(new Edge(i, j, result));


			}

			
		}


		parent = new int[n];

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

		int useEdge = 0;

		double result = 0;

		while (useEdge < n - 1) {
			Edge now = pq.poll();

			if (find(now.s) != find(now.e)) {
				union(now.s , now.e);

				result = result + now.v;
			
				useEdge++;
			}
		}

		System.out.printf("%.2f",result);
	}

	public static void union(int a , int b)
	{
		a = find(a);
		b = find(b);

		if (a != b) {
			parent[b] = a;
		}
	}

	public static int find(int a)
	{
		if (a == parent[a]) {
			return a;
		}else{
			return parent[a] = find(parent[a]);
		}
	}


	public static double distance( Node n1 , Node n2)
	{

		double dx = n1.x - n2.x ;
		double dy = n1.y - n2.y ;

		return Math.sqrt((dx * dx) + (dy * dy));
	}
}

먼저 점의 개수 n을 입력 받고, n개의 좌표를 입력 받아서 nodes 배열에 저장한다.입력 받은 좌표들 간의 거리를 계산하여 모든 가능한 간선을 우선순위 큐(pq)에 저장한다. 이때 거리가 짧은 간선이 먼저 나오도록 정렬된다.parent 배열을 생성하고, 각 노드의 부모를 자기 자신으로 초기화한다.
크루스칼 알고리즘을 이용하여 최소 신장 트리를 구성한다. 간선의 가중치가 작은 순서대로 간선을 선택하며, Union-Find를 통해 사이클을 만들지 않는 간선만을 선택한다.최소 비용 스패닝 트리의 비용을 소수 둘째 자리까지 출력한다.