[c++] 백준 #1774 우주신과의 교감 (190930)

< 풀이 >

모든 노드가 연결되어 있으려면! MST!가 생각날 것이다. 각 점에 대해 N(N+1)/2개의 간선의 거리를 다 구해준다. N<=1,000이므로 O(n^2)도 두렵지 않다. 이후 disjoint-set과 priority queue를 이용해서 거리 값이 작은 것부터 하나씩 disjoint-set에 union해주면 끝.

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;

vector<ii> points;
#define N_MAX 1010
int p[N_MAX];
int n_elem[N_MAX];
double ans = 0.0;

int my_find(int a){
    if (p[a] == a) return a;
    else return p[a] = my_find(p[a]);
}

void my_union(int a, int b, ll d){
    int a_root = my_find(a);
    int b_root = my_find(b);
    if(a_root != b_root){
        if (n_elem[b_root] > n_elem[a_root]){    
            p[a_root] = b_root; // a의 root를 b로
            n_elem[b_root] += n_elem[a_root];
        }
        else {
            p[b_root] = a_root;
            n_elem[a_root] += n_elem[b_root];
        }
        ans += sqrt(d);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M; cin >> N >> M;
    // N개 점의 좌표를 모두 받는다
    for(int i=0; i<N;i++){
        int x, y;
        cin >> x >> y;
        points.push_back({x, y});
    }

    priority_queue<pair<ll, ii>, vector<pair<ll, ii> >,greater<pair<ll, ii> > > pq;
    for(int i=0; i<N;i++){
        for(int j=0; j<N;j++){
            if (i==j) continue;
            ll x_diff = points[i].first-points[j].first;
            ll y_diff = points[i].second-points[j].second;
            ll d = x_diff*x_diff + y_diff*y_diff;
            pq.push({d, {i, j}}); // 점 i와 점 j 간의 거리를 pq에 저장한다.
        }
    }

    // using union & find
    for(int i=0; i<N;i++){
        p[i] = i;
        n_elem[i] = 1;
    }

    for(int i=0; i<M;i++){
        int a, b; cin >> a >> b;
        my_union(a-1, b-1, 0LL);
    }
    
    // priority queue
    while(!pq.empty()){
        auto item = pq.top();
        pq.pop();
        my_union(item.second.first, item.second.second, item.first);
    }
    cout<<fixed;
    cout.precision(2);
    cout << ans << '\n';

    return 0;
}