백준 1774 우주신과의 교감

https://www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

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

#define INF 987654321

using namespace std;


//우주신들의 좌표
pair<int, int> god[1000001];

//{dist, v}
vector<pair<double, pair<int, int>>> edge;
int parent[1001];


int findParent(int k){


    return parent[k] == k ? k : parent[k] = findParent(parent[k]);
}

bool isSame(int a, int b){

    return findParent(a) == findParent(b);

}

void mg(int a, int b){



    int pa = findParent(a);
    int pb = findParent(b);

    if (pa < pb) {
        parent[pb] = pa;
    } else {
        parent[pa] = pb;
    }


}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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


    int n, m;
    double ans = 0;



    cin >> n >> m;




    //우주신들의 좌표
    for (int i = 1; i <= n; i++) {

        cin >> god[i].first >> god[i].second;


    }

    //parent 초기화
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    //이미 연결된 통로
    for (int i = 0; i < m; i++) {

        int a, b;

        cin >> a >> b;

        //이미 연결되어 있는 통로는 union 처리를 해주어 연결을 방지
        if (!isSame(a, b)) {
            mg(a, b);

        }


    }


    //모든 우주선 간의 거리 구하기
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {

            double dist = sqrt(pow(god[j].first - god[i].first, 2) + pow(god[j].second - god[i].second, 2));

            edge.push_back({dist, {i, j}});
        }
    }



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



    for (int i = 0; i < edge.size(); i++) {


        if (!isSame(edge[i].second.first, edge[i].second.second)) {
            mg(edge[i].second.first, edge[i].second.second);
            ans += edge[i].first;

        }

    }


    cout << ans;





    return 0;
}

 

문장만 보면 헷갈려 보이지만 edge의 weight를 하는 과정이 포함되었을 뿐인 mst 문제이다

 

4개의 vertex가 있는 데 그 중 1-4가 연결되어 있고 이 외의 나머지 선을 최소 길이로 그리는 문제이다.

 

우선 이미 연결된 선을 입력 받을 때 그 edge에 속한 두 노드를 union한다.

그렇게 되면 이 다음 kruscal 알고리즘 과정에서 부모 노드가 같으므로 연결을 제외한다.

그 외 나머지 모든 노드들을 확인하면서 부모가 다르면 연결하는 방식으로 해결하였다.