[알고리즘] Java / 백준 / 별자리 만들기 / 4386

[알고리즘] Java / 백준 / 별자리 만들기 / 4386

문제

문제 링크

접근 방식

각 별들에 대한 모든 간선을 만든 후 해당 간선들의 길이를 오름차순으로 정렬하여 크루스칼 알고리즘으로 최소 신장트리를 만든다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main_4386 {

	static class Edge implements Comparable<Edge>{
		int v1;
		int v2;
		double w;
		
		Edge(int v1, int v2, double w){
			this.v1 = v1;
			this.v2 = v2;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			if(w < o.w) return -1;
			return 1;
		}
		
		
	}
	
	static int[] parent;
	static int n;
	static double stars[][];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = null;
		
		stars = new double[n][2];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			stars[i][0] = Double.parseDouble(st.nextToken());
			stars[i][1] = Double.parseDouble(st.nextToken());
		}
		
		parent = new int[n];
		makeSet();
		
		List<Edge> edgeList = new ArrayList<>();
		for(int i=0;i<n-1;i++) {
			for(int j=1;j<n;j++) {
				edgeList.add(new Edge(i,j,calDistance(stars[i], stars[j])));
			}
		}
		
		Collections.sort(edgeList);
		
		double answer = 0;
		for(int i=0;i<edgeList.size();i++) {
			Edge edge = edgeList.get(i);
			if(union(edge.v1, edge.v2)) {
				answer+= edge.w;
			}
		}
		
		System.out.println(answer);
	}
	
	public static double calDistance(double[] star1, double[] star2) {
		return Math.sqrt(Math.pow(star1[0] - star2[0],2) + Math.pow(star1[1] - star2[1], 2));		
	}
	
	public static void makeSet() {
		for(int i=0;i<n;i++) {
			parent[i] = i;
		}
	}
	
	public static boolean union(int a, int b) {
		a = find(a);
		b = find(b);
		
		if(a != b) {
			parent[b] = a;
			return true;
		}
		
		return false;
	}
	
	public static int find(int a) {
		if(a == parent[a]) return a;
		
		return parent[a] = find(parent[a]);
	}

}