[C++] 4386번 별자리 만들기 - 그래프 이론, 최소 스패닝 트리

1. 문제

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

<입력>

• - 1 -   별의 개수 \(n(1 \leq n \leq 100)\)
• - n개의 줄 -   각 별의 x, y좌표(실수) 최대 소수점 둘째 자리까지 \((0 \leq x, y \leq 1,000)\)

<출력>

• 정답 출력(절대 상태 오차는 \(10^{-2}\)까지 허용

2. 재정의

• 좌표간 거리가 비용인 그래프의 최소 스패닝 트리 구하기

3. 해결 방법

• \(n^2 = 10,000\)이므로 간선의 가중치가 \(x^2+y^2\)인 걸로 그래프 만들어서 구하기

4. 실수한 점, 개선할 점

• X

 

<코드>

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

#define pdd pair<double, double>
#define tddd tuple<double, double, double>
#define fi first
#define se second

using namespace std;

const int MAX_N = 101;

// <문제>
// 별의 개수 N
int N;
// 별의 위치 loc
vector<pdd> loc;
// 별들간 거리
vector<tddd> cost;

// union-find
int treeRoot[MAX_N], treeDegree[MAX_N];

// 최종 거리
double ans;

// 트리에서 루트노드 찾기
int findRoot(int x) {
    if(x == treeRoot[x])
        return x;
    else
        return treeRoot[x] = findRoot(treeRoot[x]);
}

// 트리 합치기
void unionTree(int x, int y) {
    x = findRoot(x), y = findRoot(y);
    
    if(x == y)
        return;
    
    if(treeDegree[x] < treeDegree[y])
        treeRoot[x] = y;
    else {
        treeRoot[y] = x;
        
        if(treeDegree[x] == treeDegree[y])
            treeDegree[x]++;
    }
}

void input() {
    // cout 소숫점 자리수 고정
    cout << fixed;
    cout.precision(2);
    
    // 초기화
    for(int i=0; i<MAX_N; i++) {
        treeRoot[i] = i;
        treeDegree[i] = 0;
    }
    
    cin >> N;
    for(int i=0; i<N; i++) {
        double x, y;
        cin >> x >> y;
        loc.push_back({x, y});
    }
    
    // 거리 계산하기
    for(int i=0; i<N; i++) {
        for(int j=0; j<i; j++) {
            double dist;
            dist = (loc[i].fi - loc[j].fi) * (loc[i].fi - loc[j].fi) + (loc[i].se - loc[j].se) * (loc[i].se - loc[j].se);
            cost.push_back({dist, i, j});
        }
    }
}

void solve() {
    // 거리에 따라 간선 오름차순 정렬하기
    sort(cost.begin(), cost.end());
    
    int linkcnt = 0;
    for(int i=0; i<cost.size(); i++) {
        tddd cur = cost[i];
        
        int s = get<1>(cur), e = get<2>(cur);
        
        // union-find를 이용해 사이클이 발생하는지 알아내기
        if(findRoot(s) == findRoot(e))
            continue;

        ans += sqrt(get<0>(cur));
        
        unionTree(s, e);
        
        // 스패닝 트리에 저장된 간선의 개수
        linkcnt++;
        
        if(linkcnt == N)
            break;
    }
    
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    solve();
    
    return 0;
}

 

<최소 스패닝 트리>

https://4legs-study.tistory.com/111

최소 스패닝 트리 (MST) : 크루스칼 알고리즘 (Kruskal Algorithm)

 

<소숫점 출력 범위 설정하기>

https://takeknowledge.tistory.com/13

C++ 소수점 출력 범위 설정하기

 

<문제 바로가기>

https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.