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

30 Jun 2023 in Study on Coding Test

최소 스패닝 트리를 활용하는 문제

정답제출코드

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

using namespace std;

int N;

struct Star
{
    int parent;
    double x;
    double y;
    bool visited = false;
};

vector<Star> Stars;
vector<pair<double, pair<int, int>>> Edges;

int find(int a)
{
	if (Stars[a].parent == a)
        return a;
	else 
        return Stars[a].parent = find(Stars[a].parent); 
}

void uni(int a, int b)
{
	a = find(a); 
	b = find(b); 
	Stars[b].parent = a; 
}

bool sameparent(int a, int b)
{
	a = find(a); 
	b = find(b);

	if (a == b)
        return true;
	else
        return false; 
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        double InputX, InputY;
        cin >> InputX >> InputY;

        Star S;
        S.parent = i;
        S.x = InputX;
        S.y = InputY;
        Stars.push_back(S);
    }

    for (int i = 0; i < N; ++i)
    {
        for (int j = i+1; j < N; ++j)
        {
            double Xlen = Stars[i].x - Stars[j].x;
            double Ylen = Stars[i].y - Stars[j].y;

            double cost = sqrt(Xlen*Xlen + Ylen*Ylen);
            
            Edges.push_back( {cost, {i, j} } );
        }
    }

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

    double result = 0;

    for (size_t i = 0; i < Edges.size(); ++i)
    {
        if (!sameparent(Edges[i].second.first, Edges[i].second.second))
        {
            uni(Edges[i].second.first, Edges[i].second.second);
            result += Edges[i].first;
        }
    }

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

    return 0;
}

문제를 보고 아! 최소 스패닝 트리겠구나 생각했다!

최소 스패닝 트리를 만들기 위해서 우선 Edge를 구성시켜야 했다.

그래서 각 별들 사이의 거리를 계산하고 Edge를 담는 vector를 만들어주었다.

for (int i = 0; i < N; ++i)
{
    for (int j = i+1; j < N; ++j)
    {
        double Xlen = Stars[i].x - Stars[j].x;
        double Ylen = Stars[i].y - Stars[j].y;

        double cost = sqrt(Xlen*Xlen + Ylen*Ylen);
        
        Edges.push_back( {cost, {i, j} } );
    }
}

그리고 필자는 크루스칼 알고리즘을 사용해서 최소 스패닝 트리를 사용하였다.

Edge를 담은 벡터를 정렬한 다음에, 크루스칼 알고리즘을 사용해 결과 값을 계산해주었다.

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

double result = 0;

for (size_t i = 0; i < Edges.size(); ++i)
{
    if (!sameparent(Edges[i].second.first, Edges[i].second.second))
    {
        uni(Edges[i].second.first, Edges[i].second.second);
        result += Edges[i].first;
    }
}

그리고 소숫점 둘째자리까지 오차가 발생하면 안되므로 아래와 같이 조치하면 끝.

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