[ 백준 4386 ] 별자리 만들기 (C++)

백준의 별자리 만들기(4386) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

주어진 N개의 별들을 최소 비용으로 모두 선을 이을 때, 그 비용이 얼마인지를 구해야 하는 문제이다.

정점과 간선이 주어지고, 해당 간선의 가중치가 주어졌을 때, 모든 정점을 이을 수 있는 간선의 최소비용을 구하는 문제이므로

최소스패닝트리(MST) 를 구현하는 과정으로 해결해보았다.

최소스패닝트리를 구하는 알고리즘은 대표적으로 '크루스칼 알고리즘' 과 '프림 알고리즘' 이 있는데, 아직 이 알고리즘들에

대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

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

[ 프림 알고리즘 알아보기(1) ]

[ 프림 알고리즘 알아보기(2) ]

위의 알고리즘 중 어떤 알고리즘을 사용해서 구현해도 상관이 없다.

또한, 문제의 구현 내용이 위에서 소개한 알고리즘들을 구현하는 내용이 전부이기 때문에, 알고리즘들에 대한 설명으로

이 글의 풀이를 대체하겠다.

소스코드는 크루스칼, 프림 2가지 버전의 소스코드 모두 첨부하겠다.

[ 크루스칼 알고리즘을 이용한 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
 
#define endl "\n"
#define MAX 110
using namespace std;
 
int N;
int Parent[MAX];
double Answer;
vector<pair<double, double>> Coord;
vector<pair<double, pair<int, int>>> Edge;
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        double a, b; cin >> a >> b;
        Coord.push_back(make_pair(a, b));
    }
}
 
double Find_Distance(double x, double y, double xx, double yy)
{
    double dx = (x - xx) * (x - xx);
    double dy = (y - yy) * (y - yy);
    double Dist = sqrt(dx + dy);
 
    return Dist;
}
 
int Find_Parent(int A)
{
    if (A == Parent[A]) return A;
    else 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;
}
 
void Solution()
{
    for (int i = 0; i < Coord.size(); i++)
    {
        double x = Coord[i].first;
        double y = Coord[i].second;
 
        for (int j = i + 1; j < Coord.size(); j++)
        {
            double xx = Coord[j].first;
            double yy = Coord[j].second;
            
            double Dist = Find_Distance(x, y, xx, yy);
            Edge.push_back(make_pair(Dist, make_pair(i, j)));
        }
    }
 
    for (int i = 0; i < N; i++) Parent[i] = i;
    sort(Edge.begin(), Edge.end());
    for (int i = 0; i < Edge.size(); i++)
    {
        double Cost = Edge[i].first;
        int Node1 = Edge[i].second.first;
        int Node2 = Edge[i].second.second;
 
        if (Same_Parent(Node1, Node2) == false)
        {
            Union(Node1, Node2);
            Answer = Answer + Cost;
        }
    }
    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;
}

[ 프림 알고리즘을 이용한 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
 
#define endl "\n"
#define MAX 110
using namespace std;
 
int N;
bool Visit[MAX];
double Answer;
vector<pair<double, double>> Coord;
vector<pair<int, double>> Node[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        double a, b; cin >> a >> b;
        Coord.push_back(make_pair(a, b));
    }
}
 
double Find_Distance(double x, double y, double xx, double yy)
{
    double dx = (x - xx) * (x - xx);
    double dy = (y - yy) * (y - yy);
    double Dist = sqrt(dx + dy);
 
    return Dist;
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        double x = Coord[i].first;
        double y = Coord[i].second;
 
        for (int j = i + 1; j < N; j++)
        {
            double xx = Coord[j].first;
            double yy = Coord[j].second;
            double Dist = Find_Distance(x, y, xx, yy);
 
            Node[i].push_back(make_pair(j, Dist));
            Node[j].push_back(make_pair(i, Dist));
        }
    }
    
    priority_queue<pair<double, int>> PQ;
    for (int i = 0; i < Node[0].size(); i++)
    {
        int Next = Node[0][i].first;
        double Cost = Node[0][i].second;
 
        PQ.push(make_pair(-Cost, Next));
    }
    Visit[0] = true;
 
    while (PQ.empty() == 0)
    {
        double Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        if (Visit[Cur] == false)
        {
            Visit[Cur] = true;
            Answer = Answer + Cost;
            
            for (int i = 0; i < Node[Cur].size(); i++)
            {
                int Next = Node[Cur][i].first;
                double nCost = Node[Cur][i].second;
 
                if (Visit[Next] == false) PQ.push(make_pair(-nCost, Next));
            }
        }
    }
    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;
}