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

모든 우주신들을 연결하는데, 연결하는 통로의 길이를 최소로하는 문제이다. 모든 우주신들을 각각 vertex로 보고, 모든 우주신들을 연결하는 Edge를 만들면, Minimun Spanning Tree를 찾는 문제로 해석할 수 있다.

MST는 Union and Find를 이용한 크루스칼 알고리즘을 이용하여 해결할 수 있다. 크루스칼 알고리즘의 시간 복잡도는 O(elog(e)) 인데, 우리는 모든 우주신들이 연결되어 있다고 가정하므로 e = (n -1)n / 2 이 된다.

n의 범위는 n <= 1000 이므로 전체 Edge의 개수는 10^6 개 이하이다. 일반적으로 10^9 번의 연산을 limit로 보기 때문에 이 방법으로 시간 내에 해결할 수 있다. 

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

int group[1010];

int getGroup(int x)
{
    if (group[x] == x)
        return x;
    return getGroup(group[x]);
}

void uni(int x, int y)
{
    int gx = getGroup(x);
    int gy = getGroup(y);
    if (gx < gy)
    {
        group[gy] = gx;
    }
    else
    {
        group[gx] = gy;
    }
}

bool isSameGroup(int x, int y)
{
    return getGroup(x) == getGroup(y);
}

class Edge
{

public:
    int x;
    int y;
    double dis;

    Edge(int x, int y, double dis)
    {
        this->x = x;
        this->y = y;
        this->dis = dis;
    }
};

struct cmp
{
    bool operator()(Edge &t, Edge &u)
    {
        return t.dis > u.dis;
    }
};

double calDis(pair<long long, long long> pos1, pair<long long, long long> pos2)
{
    return sqrt(pow(pos1.first - pos2.first, 2) + pow(pos1.second - pos2.second, 2));
}

int main()
{
    int n, m;
    cin >> n >> m;
    pair<long long, long long> pos[1010];
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        pos[i] = {x, y};
        group[i] = i;
    }

    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        uni(x, y);
    }
    priority_queue<Edge, vector<Edge>, cmp> pqEdge;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            double dis = calDis(pos[i], pos[j]);
            pqEdge.push(Edge(i, j, dis));
        }
    }
    double ans = 0;
    while (!pqEdge.empty())
    {
        Edge top = pqEdge.top();
        pqEdge.pop();
        if (!isSameGroup(top.x, top.y))
        {
            ans += top.dis;
            uni(top.x, top.y);
        }
    }
    printf("%.2f\n", ans);

    return 0;
}