백준 4386 별자리 만들기

문제 설명

백준 4386 문제 링크
n개의 별들의 좌표가 주어지면 모든 별을 이어 만드는 별자리의 최소 비용을 구한다.

문제 풀이

정점과 간선의 가중치가 주어졌고 가중치 합의 최솟값을 구하는 문제이니 최소 신장 트리 MST로 풀이하는 것을 예상할 수 있다. MST 풀이 방식에는 대표적으로 크루스칼과 프림이 있는데 크루스칼 알고리즘으로 풀이했다.

Kruskal

크루스칼 알고리즘을 짧게 설명하자면
1. 가중치를 정렬한다.
2. 가중치가 작은 것부터 선택해 정점을 연결한다.
3. 단 간선을 선택할 때 사이클이 형성되면 안된다.

사이클이 형성되지 않도록 하려면 union-find 알고리즘을 사용하면 된다. (union-find를 사용하면 직접적으로든 간접적으로든 연결된 정점은 모두 같은 부모를 가지기 때문에 연결하지 않는다.)

코드 설명

vector<pair<double, double>> stars;

stars에는 정점(별)의 x좌표 y좌표가 담긴다. stars[1].first는 1번 별의 x좌표값.

struct line{
    double dist;
    int src;
    int dst;
};

line은 src에서 dst까지의 거리 dist를 저장하는 구조체. src, dst는 별이고, dist는 두 별 사이의 거리.

    vector<line> lines;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            double tmp = pow(stars[i].first - stars[j].first, 2) 
            		+ pow(stars[i].second - stars[j].second, 2);
            tmp = sqrt(tmp);
            line l = {tmp, i, j};
            lines.push_back(l);
        }
    }
    sort(lines.begin(), lines.end(), comp);

lines에 line을 계산해 담는다. 0 -> 1, 1 -> 0을 모두 담는 것이 아니라 인덱스를 기준으로 작은별에서 큰별로 가는 간선만 계산해서 담았다.
마지막으로 dist를 기준으로 정렬한다. (전체 코드에서 comp 참고)

    for (int i = 0; i < lines.size(); i++) {
        double cost = lines[i].dist;
        int star1 = lines[i].src;
        int star2 = lines[i].dst;
        if (same_parent(star1, star2) == false) {
            // star1, star2 union
            int pa = find_parent(star1);
            int pb = find_parent(star2);
            parent[pb] = pa;

            ans += cost;
        }
    }

이제 가중치가 작은 간선부터 잇는다. same_parent(star1, star2)가 true라는 것은 star1, star2가 연결되어 있다는 뜻이다. 연결되어 있지 않은 경우에는 if문 안에 있는 식을 통해 연결해주고, 연결하는데 사용된 비용은 ans에 더한다.

소스 코드

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

using namespace std;

vector<int> parent;
int n;

struct line{
    double dist;
    int src;
    int dst;
};

bool comp(line l1, line l2){
    return l1.dist < l2.dist;
}

int find_parent(int idx){
    if(idx == parent[idx]){
        return idx;
    }else{
        return parent[idx] = find_parent(parent[idx]);
    }
}

bool same_parent(int a, int b){
    int pa = find_parent(a);
    int pb = find_parent(b);
    return pa==pb;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    double a, b;
    double ans = 0;
    cin >> n;
    vector<pair<double, double>> stars;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        stars.push_back(make_pair(a, b));
    }
    vector<line> lines;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            double tmp = pow(stars[i].first - stars[j].first, 2) + pow(stars[i].second - stars[j].second, 2);
            tmp = sqrt(tmp);
            line l = {tmp, i, j};
            lines.push_back(l);
        }
    }
    sort(lines.begin(), lines.end(), comp);
    parent.resize(n);

    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < lines.size(); i++) {
        double cost = lines[i].dist;
        int star1 = lines[i].src;
        int star2 = lines[i].dst;
        if (same_parent(star1, star2) == false) {
            // star1, star2 union
            int pa = find_parent(star1);
            int pb = find_parent(star2);
            parent[pb] = pa;

            ans += cost;
        }
    }

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

    return 0;
}