[Baekjoon/C++] 4386번 - 별자리 만들기

[백준] Baekjoon Online Judge

문제로 이동

 

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

 

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

 

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

 

---

풀이

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

struct Star {
    double x = 0;
    double y = 0;
};

struct Edge {
    int start = 0;
    int end = 0;
    double weight = 0;
};

int N, parent[1001];
vector<Star> star;
vector<Edge> edge;

bool compare(Edge a, Edge b);
int findParent(int n);
double mst();

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

int findParent(int n) {
    if (parent[n] == 0 || parent[n] == n) return n;

    return parent[n] = findParent(parent[n]);
}

double mst() {
    double result = 0;

    for (int i = 0; i < edge.size(); i++) {
        int a = findParent(edge[i].start);
        int b = findParent(edge[i].end);

        if (a != b) {
            parent[b] = a;
            result += edge[i].weight;
        }
    }

    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

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

        star.push_back({ x, y });
    }

    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            double weight = sqrt(pow((star[i].x - star[j].x), 2) + pow((star[i].y - star[j].y), 2));

            edge.push_back({ i + 1, j + 1, weight });
            edge.push_back({ j + 1, i + 1, weight });
        }
    }

    sort(edge.begin(), edge.end(), compare);

    cout << round(mst() * 100) / 100 << '\n';

    return 0;
}

 

---

 

struct Star {
    double x = 0;
    double y = 0;
};

struct Edge {
    int start = 0;
    int end = 0;
    double weight = 0;
};

 코드의 가독성을 위해 구현한 구조체이다.

 

    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            double weight = sqrt(pow((star[i].x - star[j].x), 2) + pow((star[i].y - star[j].y), 2));

            edge.push_back({ i + 1, j + 1, weight });
            edge.push_back({ j + 1, i + 1, weight });
        }
    }

    sort(edge.begin(), edge.end(), compare);

 입력 받은 별의 좌표로 두 별을 이을 때 필요한 비용을 계산하여 간선을 만드는 부분의 코드이다.

 

#include <cmath>

pow(밑, 지수) : 밑을 지수만큼 곱한다.
sqrt(숫자) : 괄호 안의 숫자의 제곱근을 구한다.

 두 별 사이의 거리를 계산할 때 <cmath>의 pow와 sqrt를 사용하였다.

 

---

 

cout << round(mst() * 100) / 100 << '\n';

 답을 출력하는 부분의 코드이다.

 

#include <cmath>

round(숫자) : 괄호 안의 숫자를 반올림한다.

 <cmath>의 round 함수를 사용했는데, round 함수는 소수 1의 자리에서 반올림하여 소수를 날려 버린다. 그렇기에 소수점 둘째자리까지의 숫자를 출력하기 위해 round의 괄호 안의 숫자에 100을 곱하도록 했다. 그리고 round의 결과로 나온 숫자에 100을 나눈 것을 출력하도록 했다.