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

4386번: 별자리 만들기

기본적인 MST (최소스패닝트리) 문제!

나는 입력을 잘 못 받아두고 왜 안되냐고 고통받다가 나중에 발견했다 :(

프림이나 크루스칼 둘 중에 한가지를 사용해서 풀 수 있는데,

나는 프림을 사용해서 풀었다.

크루스칼은 union, findSet을 구현하기가 너무 귀찮았다  =(:з」∠)_ 

 

풀이 방법

1. 입력받은 좌표를 이용해 다른 별과의 거리를 구한다.

2. 첫번째 별부터 시작!
   다른 별들의 번호와 첫번째별과의 거리를 Edge 객체로 만들어 PQ에 넣는다. 
   방문한 별의 개수(cnt)를 1로 초기화한다.

3. PQ의 현재 별의 방문 배열을 확인하고, 방문하지 않았다면 거리를 더하고 별의 개수(cnt)를 늘린다.

4. 방문하지 않는 별들과 현재 별의 거리를 이용해 Edge 객체로 만들어 PQ에 넣는다. 
   

5. cnt가 N개가 되었다면 모든 별을 이었기 때문에 답을 출력하고 종료. 아니라면 3, 4번을 반복한다.

 

import java.util.*;

public class Mai {
	public static int N;
	public static double[][] stars;
	public static double[][] graph;
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		stars = new double[N][2];
		graph = new double[N][N];
		
		for (int i = 0; i < N; i++) {
			stars[i][0] = sc.nextDouble();
			stars[i][1] = sc.nextDouble();
			for (int j = 0; j < i; j++) {
				double dis = getDistance(stars[i][0], stars[i][1], stars[j][0], stars[j][1]);
				graph[i][j] = dis;
				graph[j][i] = dis;
			}
		}
		
		
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		for (int i = 1; i < N; i++) {
			pq.add(new Edge(i, graph[0][i]));
		}
		int cnt = 1;
		double sum = 0;
		boolean[] v = new boolean[N];
		v[0] = true;
		
		while(!pq.isEmpty()) {
			Edge cur = pq.poll();
			
			if (!v[cur.node]) {
				cnt++;
				sum += cur.dis;
				
				if (cnt == N) break;
				
				v[cur.node] = true;
				for (int i = 0; i < N; i++) {
					if (!v[i]) {
						pq.add(new Edge(i, graph[cur.node][i]));
					}
				}
			}
		}
		System.out.printf("%.2f",sum);
	}
	
	public static double getDistance(double x1, double y1, double x2, double y2) {
		return Math.sqrt(Math.pow(x2-x1, 2)+Math.pow(y2-y1, 2));
	}
	
	public static class Edge implements Comparable<Edge> {
		int node;
		double dis;
		public Edge(int node, double dis) {
			this.node = node;
			this.dis = dis;
		}
		@Override
		public int compareTo(Edge o) {
			return Double.compare(dis, o.dis);
		}
	}
}