8주차(최소신장트리) - [C++]백준4386 별자리 만들기

09 May 2022 in Study on Algorithm

백준4386 별자리 만들기 링크

문제

예제 입력

---

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

int arr[101];
vector<pair<int, int>> star;
vector<pair<double, pair<int, int>>> vec;

// 원소가 속한 집합 찾기  
int find(int x) {
    if (arr[x] != x) arr[x] = find(arr[x]);
    return arr[x];
}

// 두 원소 집합 합치기  
void Union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a < b) arr[b] = a;
    else arr[a] = b;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) arr[i] = i;

    for (int i = 0; i < n; i++) { // 정점 좌표
        double a, b;
        cin >> a >> b;
        star.push_back({ a, b });
    }

    // 간선 만들기
    for (int i = 0; i < n -1; i++) {
        for (int j = i+1; j < n; j++) {
            double e = sqrt(pow(star[i].first - star[j].first, 2) + pow(star[i].second - star[j].second, 2));
           vec.push_back({ e, {i+1,j+1} });
        }
    }
    sort(vec.begin(), vec.end());

    // 크루스칼 알고리즘
    double cost = 0;
    for (int i = 0; i < vec.size(); i++) {
        if (find(vec[i].second.first) != find(vec[i].second.second)) {
            Union(vec[i].second.first, vec[i].second.second);
            cost += vec[i].first;
        }
    }
    cout << fixed << setprecision(2) << cost;
    // 소수점 아래 6자리 cout설정(반올림) = fixed
    // 소수점 아래 X자리까지 보임 = setprecision(X)
    // printf("%.2f", cost) 와 같음
    // 버림 = floor() 올림 = ceil()

    //setprecision(int n)	실수의 정밀도 설정
    //setw(int n)	출력되는 영역의 폭 설정
    //setfill(char c)	출력하고 남은 부분을 c로 채움
    //fixed	실수를 고정된 부동소수점 형식으로
    //showpoint	실수의 소수점 부분이 없어도 소수점 아래에 0을 표시
    //left	왼쪽 정렬
    //right	오른쪽 정렬
    //boolalpha	bool 값을 1, 0이 아닌 true, false로 출력
    //showbase	진법기호(16진수의 경우 0x, 8진수의 경우 0)도 출력
    //dec	정수를 10진수로 출력
    //hex	정수를 16진수로 출력
    //oct	정수를 8진수로 출력
}

설명

이 문제는 별의 위치가 주어지며 이 별들로 별자리를 만드는데 드는 최소 비용을 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector와 iomanip를 사용하여 구현했습니다. 별들의 위치 정보를 입력 받아 MST로 최소 비용을 구해야하는데 간선이 주어지지 않아서 두 위치 상에 거리를 구하는 공식 sqrt(pow(x1-x2)+pow(y1-y2))로 구하여 직접 만들어 줬습니다. 그 상태에서 크루스칼 알고리즘을 사용하기 위해서 간선을 오름차순으로 정렬하고 최소신장트리를 구하였습니다. 그리고 최소 비용을 출력할때 소수점 둘째자리 까지 허용하기 때문에 cout출력문에 설정을 2자리까지 고정시켜 출력합니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

<iomanip>
-fixed : 실수를 고정된 부동소수점 형식으로
-setprecision(n) : 실수의 정밀도 설정

<cmath>
-pow(val, n) : val의 n제곱
-sqrt(val) : 루트

---

결과