[백준BOJ] 4386번 별자리 만들기.java

 

백준 저지에서 를 자바를 통해 풀어 보았다. 

 

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

4386번: 별자리 만들기

4386번 별자리 만들기.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

4386번 별자리 만들기 

문제

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

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

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

설명

최소 스패닝 트리를 통해 풀 수 있는 문제이다.

 

최소 스패닝 트리는 대표적으로 우선순위 큐를 이용하는 프림 알고리즘과 유니온 파인드를 이용하는 크루스칼 알고리즘이 있다. 유니온 파인드에 더 익숙해지고 싶어서 크루스칼 알고리즘을 사용해서 풀었다.

 

모든 별을 이어서 만들 수 있는 모든 간선을 만들고 가중치 기준 오름차순으로 정렬한다. 다음 유니온 파인드를 통해 크루스칼 알고리즘을 적용하여 최소 스패닝 트리를 구하고 이 때 가중치의 합이 곧 최소 비용이다.

코드

//4386번 별자리 만들기.java
package boj20211222;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class 별자리_만들기_4386 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static class edge implements Comparable<edge>{
    	int from;
    	int to;
    	double val;
    	edge(int from, int to, double val){
    		this.from = from;
    		this.to = to;
    		this.val = val;
    	}
    	
		@Override
		public String toString() {
			return "edge [from=" + from + ", to=" + to + ", val=" + val + "]";
		}

		@Override
		public int compareTo(edge o) {
			return Double.compare(this.val, o.val);
		}
    	
    }
	public static void main(String[] args) throws NumberFormatException, IOException {
		int n = Integer.parseInt(br.readLine());
		int[] parent = new int[n+1];
		double[][] node = new double[n+1][2];
		List<edge> edges = new ArrayList<edge>();
		
		for(int i=1;i<=n;i++) {
			parent[i]=i;
			st = new StringTokenizer(br.readLine()," ");
			node[i][0] = Double.parseDouble(st.nextToken());
			node[i][1] = Double.parseDouble(st.nextToken());
		}
		for(int i=1;i<=n;i++) {
			for(int j=i+1;j<=n;j++) {
				double val = Math.sqrt((node[i][0]-node[j][0])*(node[i][0]-node[j][0])+(node[i][1]-node[j][1])*(node[i][1]-node[j][1]));
				edges.add(new edge(i, j, val));
			}
		}
		Collections.sort(edges);
		
		double answer=0;
		for(int i=0;i<edges.size();i++) {
			int from = find(edges.get(i).from, parent);
			int to = find(edges.get(i).to, parent);
			if(from!=to) {
				answer += edges.get(i).val;
				union(from, to, parent);
			}
		}
		System.out.println(answer);
	}
	
	static int find(int x, int[] parent) {
		if(x==parent[x]) {
			return x;
		}
		parent[x] = find(parent[x],parent);
		return parent[x];
	}
	
	static void union(int x, int y, int[] parent) {
		x = find(x, parent);
		y = find(y, parent);
		if(x>y)parent[x]=y;
		else parent[y]=x;
	}
}