[백준][C++] 4386번: 별자리 만들기 <233>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

4386번: 별자리 만들기

생각의 흐름

최소 신장 트리(MST)가 가장 먼저 떠오르는 문제이다.

 

다만 다른 MST 문제와 다른 점은 간선(edge) 정보가 주어지지 않는다는 점 이다.

따라서 사용자가 직접 모든 간선을 만들어 주어야 한다.

 

따라서나는 2중 for문을 통해 모든 정점마다 확인하여 간선을 만들어 주었다.

for(int i = 0; i < pVector.size(); i++) {
    Point& nowP = pVector[i];

    for(int j = i+1; j < pVector.size(); j++) {
        double dist = nowP.getDistance(pVector[j]);
        lVector.push_back(Line(i, j, dist));
    }
}

이렇게 간선을 직접 모두 만든 후, MST 알고리즘을 적용시키면 된다.

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 101

int N;

class Point{
public:
    double x, y;
public:
    Point(double x, double y): x(x), y(y) {};

    double getDistance(Point other) {
        double dx = (x - other.x) * (x - other.x);
        double dy = (y - other.y) * (y - other.y);
        return sqrt(dx + dy);
    }
};

class Line{
public:
    int a, b;
    double dist;
public:
    Line(int a, int b, double dist) : a(a), b(b), dist(dist) {}

    bool operator < (const Line& temp) const {
        return this->dist < temp.dist;
    }
};

int parent[MAX];

int find(int u) {
    if(parent[u] == u) {
        return u;
    }
    return parent[u] = find(parent[u]);
}

void Join(int a, int b) {
    int ap = find(a);
    int bp = find(b);

    if(ap != bp) {
        parent[ap] = bp;
    }
}

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

    vector<Point> pVector;
    vector<Line> lVector;

    for(int i = 0; i < MAX; i++) {
        parent[i] = i;
    }

    double a, b;
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> a >> b;
        pVector.push_back(Point(a, b));
    }

    for(int i = 0; i < pVector.size(); i++) {
        Point& nowP = pVector[i];

        for(int j = i+1; j < pVector.size(); j++) {
            double dist = nowP.getDistance(pVector[j]);
            lVector.push_back(Line(i, j, dist));
        }
    }

    sort(lVector.begin(), lVector.end());

    vector<Line> lines;

    for(int i = 0; i < lVector.size(); i++) {
        Line line = lVector[i];

        if(find(line.a) == find(line.b)) {
            continue;
        }

        Join(line.a, line.b);
        lines.push_back(line);
    }

    double sum = 0;
    for(int i = 0; i < lines.size(); i++) {
        sum += lines[i].dist;
    }
    cout.precision(3);
    cout << sum;

    return 0;
}