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

난이도 : 골드 4

 

크루스칼 알고리즘을 이용하여 풀었습니다.

별의 거리는 Math.sqrt(Math.pow(star[i].x - star[j].x, 2) + Math.pow(star[i].y - star[j].y, 2))입니다.

출처 : https://blog.naver.com/tipsware/221238349887

 

모든 별의 거리를 우선순위 큐에 넣고 크루스칼 알고리즘을 돌렸습니다.

정답 출력은 round를 이용했습니다.

---

전역 변수

int parent[] = 그룹의 대표를 나타내는 배열

함수

void main

입력을 받고 star, pq를 세팅합니다. 크루스칼을 돌리고 정답을 출력할 때 round를 이용했습니다. 0.666666이라는 수를 둘째 자리까지 출력해야 할 때를 예로 들면 0.666666*100 = 66.6666 여기서 반올림하면 67 그리고 다시 100으로 나누면 0.67이 됩니다.

즉 Math.round(n *100)/100.0입니다.

 

void union

두 개의 파라미터를 서로 연결합니다. 각 도시의 그룹 대표를 p1, p2로 구합니다.

그리고 그룹의 가장 작은 값이 그룹 대표가 되므로 작은 값을 기준으로 넣어줍니다.

 

int find

입력받은 수의 대푯값을 반환합니다.

재귀를 통해 구현했으며 재귀 과정에서 최적화를 거칩니다. 종료 시점은 파라미터의 대표가 곧 자신일 때(그룹의 가장 작은 수)입니다.

 

class Star

별의 번호, x 좌표, y 좌표를 저장합니다.

 

class Edge

간선의 정보를 저장합니다. 연결된 행성 v1, v2와 가중치 weight를 가집니다.

우선순위 큐의 타입이 될 것이므로 Comparable을 implements 해줍니다.

 

 

	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.PriorityQueue;
	import java.util.StringTokenizer;
	public class p4386 {
	static int parent[];
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer stz;
	int n = Integer.parseInt(br.readLine());
	Star star[] = new Star[n];
	parent = new int[n];
	for(int i = 0; i < n; i++)
	parent[i] = i;
	for(int i = 0; i < n; i++) {
	stz = new StringTokenizer(br.readLine());
	double a = Double.parseDouble(stz.nextToken());
	double b = Double.parseDouble(stz.nextToken());
	star[i] = new Star(i, a, b);
	}
	PriorityQueue<Edge> pq = new PriorityQueue<>();
	for(int i = 0; i < n-1; i++)
	for(int j = i+1; j < n; j++)
	pq.offer(new Edge(i, j, Math.sqrt(Math.pow(star[i].x - star[j].x, 2) + Math.pow(star[i].y - star[j].y, 2))));
	double weight = 0;
	while(!pq.isEmpty()) {
	Edge now = pq.poll();
	if(find(now.v1) != find(now.v2)) {
	union(now.v1, now.v2);
	weight += now.weight;
	}
	}
	System.out.println(Math.round(weight*100)/100.0);
	}
	public static void union(int n1, int n2) {
	int p1 = find(n1);
	int p2 = find(n2);
	if(p1 > p2)
	parent[p1] = p2;
	else
	parent[p2] = p1;
	}
	public static int find(int n) {
	if(parent[n] == n)
	return n;
	return parent[n] = find(parent[n]);
	}
	static class Star{
	int number;
	double x, y;
	Star(int n, double x, double y) {
	number = n;
	this.x = x;
	this.y = y;
	}
	}
	static class Edge implements Comparable<Edge> {
	int v1, v2;
	double weight;
	Edge(int v1, int v2, double weight) {
	this.v1 = v1;
	this.v2 = v2;
	this.weight = weight;
	}
	public int compareTo(Edge e) {
	return Double.compare(weight, e.weight);
	}
	}
	}

view raw p4386.java hosted with ❤ by GitHub