[Algorithm]Baekjoon 1774번 :: 우주신과의 교감

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
 
 
 
struct Edge
{
    int start;
    int dest;
    double dist;
};
 
int n, m;
int parents[1001] = { 0 };
pair<int, int> positions[1001];
vector<Edge> edges;
 
double GetDistnace(long long y1, long long x1, long long y2, long long x2)
{
    return sqrt(pow(y2 - y1, 2) + pow(x2 - x1, 2));
}
 
int GetParent(int node)
{
    if (parents[node] == node) return node;
    return parents[node] = GetParent(parents[node]);
}
 
bool CheckCycle(int node1, int node2)
{
    node1 = GetParent(node1);
    node2 = GetParent(node2);
 
    return node1 == node2;
}
 
void UnionParents(int node1, int node2)
{
    node1 = GetParent(node1);
    node2 = GetParent(node2);
 
    if (node1 < node2) parents[node2] = node1;
    else parents[node1] = node2;
}
 
 
bool cmp(const Edge& a, const Edge& b)
{
    return a.dist < b.dist;
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> positions[i].first >> positions[i].second;
        parents[i] = i;
    }
 
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
 
        UnionParents(a, b);
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i + 1; j <= n; ++j)
        {
            if (i == j || CheckCycle(i,j)) continue;
 
            edges.push_back({ i,j,
                GetDistnace(positions[i].first,positions[i].second,
                    positions[j].first,positions[j].second) });
        }
    }
 
    sort(edges.begin(), edges.end(), cmp);
 
    double answer = 0;
 
    for (int i = 0; i < edges.size(); ++i)
    {
        Edge& edge = edges[i];
 
        if (!CheckCycle(edge.start, edge.dest))
        {
            UnionParents(edge.start, edge.dest);
            answer += edge.dist;
        }
    }
 
    cout << fixed;
    cout.precision(2);
 
    cout << answer;
}
 
 

 

기본적으로 MST를 형성해야하는 문제인데, 추가적으로 다른점은 이미 연결된 간선이 존재한다는 것이다.

그렇기 때문에 미리 UnionParent를 해주고, 이후 크루스칼알고리즘으로 MST를 만들어줬다.

 

설명이 너무 간단한거 아닌가?라는 생각이 들 수도 있지만 정말 이게 전부다..