백준 | 4386번. 별자리 만들기 - 최소비용 신장 트리

⬛ 백준 4386번. 별자리 만들기 - 최소비용 신장 트리

https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기

문제

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

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

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

입력

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

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

출력

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

---

💚나의 풀이

• 주의할 점은 여기서는 각각의 별 n의 좌표를 (x, y)로 주는데, 그 가중치를 두 좌표 사이의 거리로 두고 있기 때문에 중복 되지 않게 이중 for문을 돌면서 다른 두 정점 간의 간선 가중치를 모두 구해놓고 pQ에 담아두어야 한다는 점이다.

//이중 for문 돌며넛 만들 수 있는 모든 간선 정보를 PQ에 담기 
for(int i=0; i<N; i++) {
    for(int j=i+1; j<N; j++) {
        //두 좌표 간 가중치 담아야 함 
        Point a = points[i];
        Point b = points[j];
        double val = Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));

        pQ.offer(new Edge(points[i].num, points[j].num, val));
    }
}

• 또한 두 점 사이의 거리 공식을 알아 두어야 한다.

두 점 a(x, y), b(x, y) 사이의 거리는 코드로 표현하면 다음과 같다. 

Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));

• 위의 과정을 거치고 나면 똑같이 최소 비용 신장 트리의 로직대로 짜주면 정답이 나온다. 여기서 좌표가 소수점까지 포함하기 때문에 변수는 double형으로 써야 하는 점도 주의하자.

package to_0911_9;

import java.util.PriorityQueue;
import java.util.Scanner;

/*4386번. 별자리 만들기 - 최소 비용 신장 트리 문풀*/
class Point {
	int num;
	double x;
	double y;
	
	Point(int num, double x, double y){
		this.num = num;
		this.x= x;
		this.y = y;
	}
}

class Edge implements Comparable<Edge>{
	int s, e;
	double val;
	
	Edge(int s, int e, double val){
		this.s = s;
		this.e = e;
		this.val = val;
	}
	public int compareTo(Edge o) {
		if(this.val < o.val) {
			return -1;
		}
		return 1;
	};
}
public class Main {
	static int N;
	static int[] parent;
	
	//find
	static int find(int a) {
		if(a == parent[a] ) return a;
		else return parent[a] = find(parent[a]);
	}
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a!=b) {
			parent[b]=a;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		
		N = kb.nextInt();
		//데이터 입력받을 때,
		Point[] points = new Point[N];
		for(int i=0; i<N; i++) {
			double x = kb.nextDouble();
			double y = kb.nextDouble();
			
			points[i] = new Point(i, x, y);//담기 
		}
		
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		//이중 for문 돌며넛 만들 수 있는 모든 간선 정보를 PQ에 담기 
		for(int i=0; i<N; i++) {
			for(int j=i+1; j<N; j++) {
				//두 좌표 간 가중치 담아야 함 
				Point a = points[i];
				Point b = points[j];
				double val = Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
				
				pQ.offer(new Edge(points[i].num, points[j].num, val));
			}
		}
		
		parent = new int[N];
		for(int i=0; i<N; i++) parent[i] = i;
		
		int useEdge = 0;
		double useCost = 0;
		
		while(useEdge< N-1) {
			Edge cur = pQ.poll();
			
			if(find(cur.s) != find(cur.e)) {
				union(cur.s, cur.e);
				useCost += cur.val;
				useEdge++;
			}
		}
		System.out.println(useCost);
	}

}