백준 1774 우주신과의 교감 (C++)

1774번: 우주신과의 교감

최소 스패닝 트리를 이용한 문제이다. 크루스칼 알고리즘을 사용하기 위해 가중치와 경로를 구하는 것이 중요한 포인트이다. 먼저 부모 노드를 나타내는 p 배열을 초기화해주고 입력으로 받은 경로를 모두 각각의 부모 노드에 지정해준다. 그리고 각 노드간의 모든 경로와 가중치를 구해주고 이를 오름차순으로 정렬해주었다. 그 후 크루스칼 알고리즘을 돌면서 가중치들을 더해 소수점 둘째자리까지 출력해주었다.
어렵지 않게 풀 수 있었던 문제였다. 단순히 모든 경로와 가중치를 구해주어 문제를 해결했지만 사실 필요한 갯수는 N-1만큼의 경로이기에 시간을 좀 더 단축시킬 수도 있을 것이다. 크루스칼 알고리즘을 사용하기 위한 이러한 방식도 인지해두자.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int N, M;
vector<pair<int, int>> n;
vector<pair<int, int>> m;
vector<pair<double, pair<int, int>>> v;
int p[1001];
double result = 0;

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

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a != b) p[a] = b;
}

bool sameParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a == b) return true;
    else return false;
}

void findRoot() {
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            long long a = (long long) pow(n[i].first - n[j].first, 2);
            long long b = (long long) pow(n[i].second - n[j].second, 2);
            double c = (double) sqrt(a + b);
            
            v.push_back({ c, {i + 1,j + 1} });
        }
    }
}

void solution() {
    for (int i = 1; i <= N; i++) {
        p[i] = i;
    }

    for (int i = 0; i < M; i++) {
        int a = m[i].first;
        int b = m[i].second;

        if (a > b) swap(a, b);

        unionParent(a, b);
    }

    findRoot();

    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++) {
        int a = v[i].second.first;
        int b = v[i].second.second;
        double c = v[i].first;

        if (!sameParent(a, b)) {
            unionParent(a, b);
            result += c;
        }
    }

    cout << fixed;
    cout.precision(2);
    cout << result;
}

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

    cin >> N >> M;

    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        n.push_back({ a,b });
    }

    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        m.push_back({ a,b });
    }

    solution();

    return 0;
}