문제

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

  • 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
  • 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

문제 링크

입력

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

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

출력

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

예제

입력
3
1.0 1.0
2.0 2.0
2.0 4.0

출력
3.41

나의 접근 방법

모든 별이 직/간접적으로 이어져 있어야 하고 최소 비용으로 만들어야 하기 때문에 사이클이 발생해서는 안 된다는 것을 알 수 있다.
따라서 최소 스패닝 트리를 구하는 것과 같은 의미이므로 크루스칼 알고리즘을 이용하여 문제를 해결했다.
n이 최대 100밖에 되지 않기 때문에 입력을 받은 후 모든 정점들 간의 거리를 계산하여 Heap에 넣은 후 사용된 edge가 별의 개수와 같아졌을 때 반복문을 종료시켰다.

코드

#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<functional>
using namespace std;

int parents[101] = {0, };
struct info{
  int from;
  int to;
  double d;
};

struct cmp{
  bool operator()(info t, info u){
    return t.d > u.d;
  }
};
int find(int u){
  if(parents[u] == u) return u;
  return parents[u] = find(parents[u]);
}

void merge(int u, int v){
  u = find(u); v = find(v);
  if(u == v) return;
  parents[v] = u;
}

int main(void){
  int N, count = 0; cin>>N;
  double result = 0;
  for(int i = 0 ; i<N ; i++) parents[i] = i;
  vector<pair<double, double>> inputs;
  vector<vector<double>> dist(N, vector<double>(N));
  priority_queue<struct info, vector<struct info>, cmp> pq;
  for(int i = 0 ; i<N ; i++){
    double x, y; cin>>x>>y;
    inputs.push_back({x, y});
  }
  for(int i = 0 ; i<N ; i++){
    pair<double, double> now = inputs[i];
    for(int j = 0 ; j<N ; j++){
      pair<double, double> next = inputs[j];
      if(i == j){
        dist[i][j] = 1000000000;
        continue;
      }
      double x = next.first - now.first, y = next.second - now.second;
      dist[i][j] = sqrt(x*x + y*y);
      pq.push({i,j,dist[i][j]});
    }
  }
  while(!pq.empty()){
    if(count == N) break;
    struct info now = pq.top();
    pq.pop();
    if(find(now.from) == find(now.to)) continue;
    merge(now.from, now.to);
    result += now.d;
    count++;
  }
  cout<<fixed;
  cout.precision(2);
  cout<<result;
  return 0;
}