[BOJ4386] 별자리 만들기

또 최소 비용.

최소 비용은 MST이라고 생각이 나야 한다.

 

어떻게 구현하기 전 필요한 것은 star의 좌표 구조체와 간선 구조체가 필요하다.

비용은 최소 비용이므로,

 

bool cmpCost(edge a, edge b)
{
	return a.cost < b.cost;
}

cost는 두 좌표 사이의 거리가 비용이므로, 좌표와 비용을 간선 구조체에 저장한다.

 

그리고, 정렬은 비용 기준으로 해야 한다. 그래야 칼퇴 가능

 

소스는 참고용으로 

/*
하늘에 n개의 별들을 이어서 별자리를 만들려고 한다.
- 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
- 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
*/
// 알고리즘: MST

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

using namespace std;

struct star
{
    double x, y;
};

struct edge
{
    int from, to;
    double cost;
};

int parent[101];
vector<star> s;
vector<edge> e;

bool cmpCost(edge a, edge b)
{
    return a.cost < b.cost;
}

int find(int x)
{
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return;
    parent[y] = x;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        double x, y;
        cin >> x >> y;
        s.push_back({x, y});
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = i+1; j < n; j++)
        {
            double cost = sqrt(pow(s[i].x - s[j].x, 2) + pow(s[i].y - s[j].y, 2));
            e.push_back({i, j, cost});
        }
    }
    sort(e.begin(), e.end(), cmpCost);
    for(int i = 0; i < n; i++) parent[i] = i;
    double ans = 0;
    for(int i = 0; i < e.size(); i++)
    {
        if(find(e[i].from) != find(e[i].to))
        {
            merge(e[i].from, e[i].to);
            ans += e[i].cost;
        }
    }
    cout << fixed;
    cout.precision(2);
    cout << ans;
    return 0;
}

이거도 기네

ㅋㅋㅋㅋㅋㅋㅋ