도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
- 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
- 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
import java.io.*;
import java.util.*;
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//N 입력 받기
int n = Integer.parseInt(br.readLine());
//별들의 좌표 입력 받기
double[][] stars=new double[n][2];
for(int i=0; i<n; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
stars[i] = new double[]{Double.parseDouble(st.nextToken()), Double.parseDouble(st.nextToken())};
}
//간선 정보 저장할 공간 초기화 및 저장
double[][] edges=new double[n*(n-1)/2][3];
int index=0;
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
edges[index++]=new double[]{i, j, calculateDistance(stars[i], stars[j])};
//부모 배열 초기화
int[] union=new int[n];
IntStream.range(0, n).forEach(o->union[o]=o);
//{노드 A, 노드 B, 거리} 중 거리를 기준으로 하는 최소힙
PriorityQueue<double[]> pq=new PriorityQueue<>(Comparator.comparingDouble(o->o[2]));
//간선 전부 넣기
pq.addAll(List.of(edges));
//index가 노드의 갯수-1 만큼 되면 스패닝 트리 완성
double answer=0;
index=0;
while(!pq.isEmpty()){
double[] ptr=pq.poll();
//싸이클을 형성하면 continue
if(union[(int) ptr[0]]==union[(int) ptr[1]])
continue;
//간선 채택
answer+=Math.sqrt(ptr[2]);
//부모 합치기
int parent=Math.min(union[(int) ptr[0]], union[(int) ptr[1]]);
int child=Math.max(union[(int) ptr[0]], union[(int) ptr[1]]);
for(int i=0; i<n; i++)
if(union[i]==child)
union[i]=parent;
if(index==n-1)
break;
}
bw.write(answer+"\n");
bw.flush();
}
//거리 계산
public static double calculateDistance(double[] a, double[] b){
return Math.pow((a[0]-b[0]), 2)+Math.pow(a[1]-b[1], 2);
}
}
모든 별 사이의 거리를 계산해둔 뒤에 크루스칼 알고리즘을 사용한다.
😁