[Java] 4386. 별자리 만들기

www.acmicpc.net/problem/4386

4386번: 별자리 만들기

문제

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

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

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

입력

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

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

출력

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

---

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

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static final double INF = Double.MAX_VALUE;
	static double res;
	static class XY{
		double x, y;

		public XY(double x, double y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "XY [x=" + x + ", y=" + y + "]";
		}
		
	}
	static ArrayList<XY> list = new ArrayList<>();
	static boolean isSelected[];
	static double MinArr[];
	public static void main(String[] args) throws Exception{
		int N = Integer.parseInt(in.readLine());
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			double x = Double.parseDouble(st.nextToken());
			double y = Double.parseDouble(st.nextToken());
			list.add(new XY(x, y));
		}
		double map[][] = new double[N][N];
		isSelected = new boolean[N];
		MinArr = new double[N];
		Arrays.fill(MinArr, INF);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = getLength(i, j);
			}
		}
		
		MinArr[0] = 0;
		int cnt = 0;
		while(true) {
			int idx = 0;
			double val = Double.MAX_VALUE;
			for (int i = 0; i < N; i++) {
				if(!isSelected[i] && MinArr[i] < val) {
					val = MinArr[i];
					idx = i;
				}
			}
			
			isSelected[idx] = true;
			res += MinArr[idx];
			if(++cnt == N) break;
			for (int i = 0; i < N; i++) {
				if(!isSelected[i] && map[idx][i] < MinArr[i]) {
					MinArr[i] = map[idx][i];
				}
			}
			
		}
		System.out.println((double)Math.round(res*100)/100);
		
	}
	private static double getLength(int i, int j) {
		XY one = list.get(i);
		XY two = list.get(j);
		
		return Math.sqrt(Math.pow(one.x-two.x, 2)+Math.pow(one.y-two.y, 2));
	}

}