[자바] 백준 4386 - 별자리 만들기

각 별(=노드)의 위치를 좌표평면 상에 주고, 별들 간 거리는 알아서 계산한 다음에, 최소 스패닝 트리를 구하는 문제.

n이 최대 100이기 때문에 거리를 구하는 데에는 100x99의 연산이 필요하니까 큰 문제는 없을 것 같은데 좀 귀찮네 ㅎㅎ

게다가 실수값이라 더 귀찮다.

 

 

1. 배열을 만들어서 각 별들의 x,y 좌표 담아두기

2. 이중 for문 이용해서 각 별들간 거리 구하고 그 값들은 PriorityQueue에 담아두기

3. PriorityQueue를 while문으로 탐색해서 최소 스패닝 트리값 구하기

 

---

DefimalFormat이라는 클래스를 써봤다. 

그리고 다른 통과자들 코드를 보니까 PQ 이용하는 것보다는 ArrayList가 더 빠른가보다.

/* 2021.01.05(화) */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.text.DecimalFormat;
import java.util.PriorityQueue;

public class Main {
	
	static int[] parent;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		DecimalFormat form = new DecimalFormat("#.##");
		
		int n = Integer.parseInt(br.readLine().trim());
		double[][] position = new double[n+1][2];
		
		//부모값 초기화 
		parent = new int[n+1];
		for(int i=0;i<=n;i++) parent[i]=i;
		
		//좌표평면 상 위치 기록해두기
		String[] str;
		for(int i=1;i<=n;i++) {
			str = br.readLine().trim().split(" ");

			position[i][0] = Double.parseDouble(str[0]);
			position[i][1] = Double.parseDouble(str[1]);
		}
		
		//간선 간 거리 구하기
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		Double firstX, firstY;
		Double secX, secY;
		for(int i=1;i<=n;i++) {
			firstX = position[i][0];
			firstY = position[i][1];
			for(int j=i+1;j<=n;j++) {
				secX = position[j][0];
				secY = position[j][1];
				
				double weight = getDistance(firstX, firstY, secX,secY);
				pq.add(new Edge(i,j,weight));
				
			}
		}
		
		//MST 찾기 
		Edge currEdge;
		double total = 0.00;
		while(!pq.isEmpty()) {
			currEdge = pq.poll();
			
			if(hasSameParent(currEdge.s, currEdge.e)) continue;
			
			union(currEdge.s, currEdge.e);
			total += currEdge.w;
			
		}
		
		System.out.println(form.format(total));

	}
	
	private static double getDistance(Double firstX, Double firstY, Double secX, Double secY) {
		double x = Math.pow(Math.abs(firstX-secX),2);
		double y = Math.pow(Math.abs(firstY-secY),2);
		
		return Math.sqrt(x+y);
	}

	private static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		//작은 숫자의 parent로 통일시켜주기로 했으니까,
		//최종적으로 노드들은 parent가 전부 1일 것
		//(1부터 V까지 모두 연결시켜야 하니까!)
		if(x>y) parent[x] = y;
		else parent[y] = x;
		
	}

	private static boolean hasSameParent(int s, int e) {
		int sParent = find(s);
		int eParent = find(e);
		
		if(sParent==eParent) return true;
		else return false;
	}

	private static int find(int x) {
		
		if(parent[x]==x) return x;
		return parent[x] = find(parent[x]);
	}

	static class Edge implements Comparable<Edge>{
		
		int s;
		int e;
		double w;
		
		public Edge(int s, int e, double w) {
			this.s = s;
			this.e = e;
			this.w = w;
		}
		
		@Override
		public int compareTo(Edge o) {
			return (int)(this.w-o.w);
		}
	}
}