[Java] 백준 4386번 : 별자리 만들기

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

예제 입력 1

3
1.0 1.0
2.0 2.0
2.0 4.0

예제 출력 1

3.41

 

소스코드

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

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;

	private static int N;
	private static Node [] node;
	private static ArrayList<Edge> edges=new ArrayList<>();
	private static int [] parent;

	static class Node {
		double r, c;

		public Node(double r, double c) {
			super();
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Node [r=" + r + ", c=" + c + "]";
		}
		
	}

	static class Edge implements Comparable<Edge> {
		int start, end;
		double dist;

		public Edge(int start, int end, double dist) {
			super();
			this.start = start;
			this.end = end;
			this.dist = dist;
		}

		@Override
		public String toString() {
			return "Edge [start=" + start + ", end=" + end + ", dist=" + dist + "]";
		}

		@Override
		public int compareTo(Edge o) {
			if(this.dist<o.dist) return -1;
			return 1;
		}

	}

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

		bf = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(bf.readLine());
		node = new Node[N];
		parent=new int[N];
		makeSet();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());
			double r = Double.parseDouble(st.nextToken());
			double c = Double.parseDouble(st.nextToken());
			node[i]=new Node(r, c);
		}
		
		for(int i=0;i<N;i++) {
			for(int j=i+1;j<N;j++) {
				double dist=distance(node[i], node[j]);
				edges.add(new Edge(i, j, dist));
			}
		}
		
		Collections.sort(edges);
		double result=0;
		for(int i=0;i<edges.size();i++) {
			int start=edges.get(i).start;
			int end=edges.get(i).end;
			double dist=edges.get(i).dist;
			
			if(findParent(start)!=findParent(end)) {
				result+=dist;
				union(start, end);
			}
		}
		System.out.println(result);
	}

	public static void makeSet() {
		for(int i=0;i<N;i++) parent[i]=i;
	}
	
	public static int findParent(int a) {
		if(a==parent[a]) return a;
		return parent[a]=findParent(parent[a]);
	}
	
	public static void union(int a, int b) {
		int aRoot=findParent(a);
		int bRoot=findParent(b);
		
		parent[bRoot]=aRoot;
		return;
	}
	
	public static double distance(Node node1, Node node2) {
		return Math.pow((node1.r-node2.r)*(node1.r-node2.r)+(node1.c-node2.c)*(node1.c-node2.c), 0.5);
	}
}

1. 모든 두 점 사이의 거리를 구하여 Edge 리스트에 저장합니다.

2. Edge 리스트를 거리 오름차순으로 정렬합니다.

3. Edge 리스트에서 거리가 가장 짧은 것부터 크루스칼 알고리즘을 이용하여 최소 간선 비용을 구합니다.