[백준 1774번] 우주신과의 교감

문제 링크: https://www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

<문제 풀이> 최소 스패닝 트리, 크루스칼 알고리즘

 

모든 서로 다른 두 정점 사이에 거리를 구해서 간선에 추가하고 크루스칼 알고리즘을 이용하여 최소 스패닝 트리를 찾으면 됩니다.

 

[주의할 점]

1. 이미 연결된 통로를 입력받을 때, 중복된 간선이 들어올 수 있습니다.

 

예를 들어, 1-2와 2-1은 동일한 간선을 나타냅니다. 이 경우를 고려하지 않으면 현재까지 최소 스패닝 트리에 추가된 간선의 수를 계산할 때 문제가 생길 수 있습니다.

 

2. 좌표 값의 최댓값이 10^6이므로, 거리를 계산할 때 오버플로우를 방지하기 위해 long long 자료형을 사용해야 합니다.

 

<C++소스코드>

 

#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
#include<tuple>
#include<cmath>
using namespace std;

typedef long long ll;

int n, m;
pair<ll, ll> arr[1001];
int parents[1001];
vector<tuple<double, ll, ll> > edge;

int Find(int x) {
    if (parents[x] == x) return x;
    return parents[x] = Find(parents[x]);
}

void Union(int x, int y) {
    int xParents = Find(x);
    int yParents = Find(y);
    if (xParents < yParents) parents[xParents] = yParents;
    else parents[yParents] = xParents;
}


int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        parents[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        int x, y; cin >> x >> y;
        arr[i] = { x, y };
    }
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        if (Find(u) == Find(v)) continue;
        cnt++;
        Union(u, v);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (Find(i) == Find(j)) continue;
            double dist = sqrt((arr[i].first - arr[j].first) * (arr[i].first - arr[j].first) + (arr[i].second - arr[j].second) * (arr[i].second - arr[j].second));
            edge.push_back({ dist, i, j });
        }
    }
    sort(edge.begin(), edge.end());
   
    double ans  = 0;
    for (auto& e : edge) {
        double dist;
        int u, v;
        tie(dist, u, v) = e;
        if (Find(u) == Find(v))continue;
        Union(u, v);
        cnt++;
        ans += dist;
        if (cnt == n - 1) break;
    }
    cout << fixed;
    cout.precision(2);
    
    cout << ans;

    return 0;
}