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

백준의 우주신과의 교감(1774) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

본인은 이 문제를 최소스패닝트리(Minimal Spanning Tree)를 구현하는 방식으로 접근했다.

주어진 좌표들을 모두 연결하면서 그 길이가 최소가 되는 값을 구해야 하는 과정이 MST를 구하는 과정과 비슷하다고 생각했기 때문이다. MST를 구현하는 방법 중에서도 크루스칼 알고리즘을 이용해서 구현해보았다.

아직 크루스칼 알고리즘에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 크루스칼 알고리즘 알아보기(Click) ]

크루스칼 알고리즘을 이용해서 구현하면 되는데 ! 구현하기 전에 우선적으로 처리해줘야 할 부분이 하나 있다.

바로, "이미 연결되어 있는 통로"에 대한 처리이다. 이 부분은 크루스칼 알고리즘을 본격적으로 구현하기 전에 따로 Union작업을

통해서 이미 연결되어 있는 통로라는 것을 알 수 있도록 만들어 주었다.

전체적인 구현 내용이 위에서 링크를  걸어놓은 크루스칼 알고리즘만 알고 있더라도 충분히 구현할 만한 내용이니 별도의 설명 없이 소스코드를 첨부하겠다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N, M;
int Parent[MAX];
double Answer;
vector<pair<int, int>> Coord;
vector<pair<int, int>> Connect;
vector<pair<double, pair<int, int>>> Edge;
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++) Parent[i] = i;
    for (int i = 0; i < N; i++)
    {
        int a, b; cin >> a >> b;
        Coord.push_back(make_pair(a, b));
    }
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Connect.push_back(make_pair(a, b));
    }
}
 
int Find_Parent(int A)
{
    if (A == Parent[A]) return A;
    return Parent[A] = Find_Parent(Parent[A]);
}
 
bool Same_Parent(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
    if (A == B) return true;
    return false;
}
 
void Union(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
    Parent[B] = A;
}
 
double Find_Distance(int x, int y, int xx, int yy)
{
    double dx = pow(x - xx, 2);
    double dy = pow(y - yy, 2);
    double Dist = sqrt(dx + dy);
 
    return Dist;
}
 
void Solution()
{
    for (int i = 0; i < M; i++)
    {
        int N1 = Connect[i].first;
        int N2 = Connect[i].second;
 
        if (Same_Parent(N1, N2) == false) Union(N1, N2);
    }
    for (int i = 0; i < N - 1; i++)
    {
        int x = Coord[i].first;
        int y = Coord[i].second;
        for (int j = i + 1; j < N; j++)
        {
            int xx = Coord[j].first;
            int yy = Coord[j].second;
 
            double Dist = Find_Distance(x, y, xx, yy);
            Edge.push_back(make_pair(Dist, make_pair(i + 1, j + 1)));
        }
    }
    sort(Edge.begin(), Edge.end());
    for (int i = 0; i < Edge.size(); i++)
    {
        int N1 = Edge[i].second.first;
        int N2 = Edge[i].second.second;
        double Dist = Edge[i].first;
 
        if (Same_Parent(N1, N2) == false)
        {
            Union(N1, N2);
            Answer = Answer + Dist;
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << fixed;
    cout.precision(2);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}