백준 4386번

오늘 풀어본 문제는 백준의 4386번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

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

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

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

입력

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

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

출력

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

풀이과정

1번째 시도

문제를 보고 최소 신장 트리를 구하는 문제라는 것을 알 수 있었다. 프림 알고리즘을 이용하여 최소 신장 트리의 간선의 가중치 합을 구하는 방식으로 해결을 시도하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

using pos = pair<long double, long double>;

long double distance(const pos& A, const pos& B);
long double prim (const vector<pos>& points);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    vector<pos> points(n);

    for (int i=0; i<n; i++) {
        cin >> points[i].first >> points[i].second;
    }

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

    cout << prim(points);

    return 0;
}

long double prim (const vector<pos>& points) {
    size_t n = points.size();

    vector<long double> distFromTree(n, INT_MAX);
    vector<bool> visited(n, false);

    long double result = 0;

    distFromTree[0] = 0;

    for(int i=0; i<n; i++) {
        int curr = 0;
        long double minDistFromTree = INT_MAX;

        for (int candidate=0; candidate<n; candidate++) {
            if(!visited[candidate] && minDistFromTree > distFromTree[candidate]) {
                minDistFromTree = distFromTree[candidate];
                curr = candidate;
            }
        }

        visited[curr] = true;
        result += minDistFromTree;

        for (int next=0; next<n; next++) {
            if (!visited[next]) {
                distFromTree[next] = fmin(distFromTree[next], distance(points[curr], points[next]));
            }
        }
    }

    return result;
}

long double distance(const pos& A, const pos& B) {
    auto dx = A.first - B.first;
    auto dy = A.second - B.second;

    return sqrtl(dx * dx + dy * dy);
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

CLASS 5 은색 휘장을 딴 이후 남은 문제들을 풀 때, 어려운 문제들을 위주로 먼저 풀었다. 그래서 그런지 갈수록 쉬워지는 느낌이 드는 것 같다.

물론 그렇다고 해서 이 문제가 쉬운 문제였다는 것은 아니다. 최소 신장 트리를 구하는 알고리즘을 써야한다는 것만 알았고, 이를 실제로 구현하기 위해서 검색을 해가며 다시 알고리즘을 공부해야 했기 때문이다. 이제 CLASS 5는 $3$ 문제가 남았지만, 여전히 더 수련히 필요할 것 같다.

오늘의 PS는 여기까지…?

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

← Previous Post Next Post →