아이디어

• n개 정점의 완전 그래프에 대한 MST
  • 간선의 가중치는 두 행성 간의 거리
• n이 작고 간선 수는 많으므로 PriorityQueue를 쓰지 않는 Prim 알고리즘을 사용해봄

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int n;
	static double[] sx, sy;
	static double ans;
	static boolean[] visited;
	static double[] minDist;
	
	public static void main(String[] args) throws Exception {
		n = Integer.parseInt(rd.readLine());
		
		sx = new double[n];
		sy = new double[n];
		minDist = new double[n];
		visited = new boolean[n];
		
		for (int i=0; i<n; i++) {
			tk = new StringTokenizer(rd.readLine());
			sx[i] = Double.parseDouble(tk.nextToken());
			sy[i] = Double.parseDouble(tk.nextToken());
		}
		
		// prim - without PQ
		Arrays.fill(minDist, Double.MAX_VALUE);
		minDist[0] = 0.0;	// 0에서 시작
		
		for (int c=0; c<n; c++) {
			// 가중치 최소 비방문 정점 찾기
			int minIdx = -1;
			double min = Double.MAX_VALUE;
			for (int i=0; i<n; i++) {
				if (!visited[i] && minDist[i] < min) {
					minIdx = i;
					min = minDist[i];
				}
			}
			if (minIdx == -1) break;
			
			// 방문
			visited[minIdx] = true;
			ans += minDist[minIdx];
			
			// minIdx에서 갈 수 있는 비방문 정점에 대해 갱신
			for (int i=0; i<n; i++) {
				if (!visited[i] && minIdx != i)
					minDist[i] = Math.min(minDist[i], dist(minIdx, i));
			}
		}
		
		System.out.println(ans);
	}
	
	static double dist(int i, int j) {
		double dx = sx[i] - sx[j];
		double dy = sy[i] - sy[j];
		return Math.sqrt(dx * dx + dy * dy);
	}
}

메모리 및 시간

• 메모리: 14120 KB
• 시간: 128 ms

리뷰

• n이 작을 때는 PQ를 안 쓰는게 더 빠를 수 있다.