[백준] 4386 별자리 만들기 - Kruskal 알고리즘

문제

---

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

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

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

 

 

 

풀이

---

이 문제는 최소 스패닝트리를 이용해 푸는 문제다.

 

필자는 크루스칼 알고리즘을 이용해서 문제를 풀었다.

 

알고리즘 순서는 다음과 같다.

1. 모든 점과 점의 사이 거리를 구해 PriorityQueue에 넣어준다.
2. 사이 거리가 작은 순부터 차례대로 사이클을 형성하지 않는 거리를 더해준다.
3. 총 더해진 간선의 수가 n - 1 개가 되면 반복문을 종료한다.

위의 3가지 과정을 거치면 된다.

 

사이클을 형성하는지 확인하기 위해서는 Union-Find 알고리즘을 이용해서 풀면 된다.

static int find(int[] parent, int v) {
	
	if(parent[v] == v) {
		return v;
	}
	
	return parent[v] = find(parent, parent[v]);		
}

static boolean union(int[] parent, int a, int b) {
	a = find(parent, a);
	b = find(parent, b);
	
	if(a == b) {
		return false;
	}
	
	if(a > b) {
		parent[a] = b;
	}
	else {
		parent[b] = a;
	}
	
	return true;
}

위의 코드가 Union-Find 알고리즘이다.

find 메소드를 이용해 현재 연결 돼 있는 점의 부모가 같다면 사이클이기 때문에 false 를 return 하여 값을 더하지 않게 한다.

 

같지 않다면 두 부모를 조정하여 연결 된 간선임을 표시한다.

 

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int n;
	static star[] stars;
	static double answer;

	static StringBuilder sb = new StringBuilder();

	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		n = parseInt(br.readLine());
		stars = new star[n];
		
		for(int i = 0; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			double x = Double.parseDouble(st.nextToken());
			double y = Double.parseDouble(st.nextToken());
			
			stars[i] = new star(x, y);
		}
		
		PriorityQueue<line> pq = new PriorityQueue<>();
		for(int i = 0 ; i < n ; i++) {
			for(int j = i + 1 ; j < n ; j++) {				
				pq.add(new line(i, j, calculator(stars[i], stars[j])));
			}
		}
		
		answer = 0;
		Kruskal(pq);
		
		System.out.println(String.format("%.2f", answer));
	}
	
	static void Kruskal(PriorityQueue<line> pq) {
		
		int[] parent = new int[n];
		for(int i = 0 ; i < n ; i++) {
			parent[i] = i;
		}
		
		int count = 0;
		while(!pq.isEmpty()) {			
			line top = pq.poll();
			
			if(union(parent, top.u, top.v)) {
				answer += top.dist;
				
				if(++count == n - 1) {
					return;
				}
			}
		}
	}
	
	static int find(int[] parent, int v) {
		
		if(parent[v] == v) {
			return v;
		}
		
		return parent[v] = find(parent, parent[v]);		
	}
	
	static boolean union(int[] parent, int a, int b) {
		a = find(parent, a);
		b = find(parent, b);
		
		if(a == b) {
			return false;
		}
		
		if(a > b) {
			parent[a] = b;
		}
		else {
			parent[b] = a;
		}
		
		return true;
	}
	
	static double calculator(star a, star b) {
		return Math.sqrt(Math.pow(Math.abs(a.x - b.x), 2) + Math.pow(Math.abs(a.y - b.y), 2));
	}
	
	static class line implements Comparable<line>{
		int u, v;
		double dist;
		
		line(int u, int v, double dist){
			this.u = u;
			this.v = v;
			this.dist = dist;
		}

		@Override
		public int compareTo(line l) {
			return Double.compare(this.dist, l.dist);
		}
	}
	
	static class star{
		double x, y;
		star(double x, double y){
			this.x = x;
			this.y = y;
		}
	}
}