4386번: 별자리 만들기

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

4386번: 별자리 만들기

각 별을 노드, 별자리 위의 선을 에지, 별과 별 사이의 거리를 가중치로 두면, 이 문제는 최소 스패닝 트리를 구하는 문제이다.

- 크루스칼 기법

#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

typedef pair<double, double> point;
typedef pair<double, pair<int, int>> edge; 

#define MAX_N 100
#define _y first
#define _x second
#define _A second.first
#define _B second.second
#define _C first

int parent[MAX_N + 1];

// root(node): node가 속한 트리의 루트 노드를 반환
int root(int node) { return (parent[node] && parent[node] % node) ? root(parent[node]) : node; }
// root(a, b): 두 노드 a와 b가 속한 트리의 루트 노드를 구해 정렬한 뒤
// 둘의 일치 여부를 반환
bool root(int &a, int &b)  {
    a = root(a);
    b = root(b);
    if (a > b) swap(a, b);

    return a == b;
}

int main() {
    // 최소 스패닝 트리의 가중치
    double ans = 0;
    // n: 노드의 수, size: 에지의 개수
    int n, size = 0;
    // 각 노드의 좌표
    point p[MAX_N];
    // 에지를 저장할 공간
    edge e[MAX_N * (MAX_N - 1) / 2];

    // 문제의 조건을 입력받은 뒤
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lf %lf", &(p[i]._y), &(p[i]._x));

    // 노드를 잇는 에지를 모두 만들어 e에 저장
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++)
        e[size++] = {sqrt(pow(p[i]._y - p[j]._y, 2) + pow(p[i]._x - p[j]._x, 2)), {i + 1, j + 1}};

    // 에지를 가중치의 오름차순으로 정렬
    sort(e, e + size);

    // 모든 에지를 이용해 최소 스패닝 트리를 구현
    for (int i = 0; i < size; i++) {
        // 현재 에지의 노드를 root 함수를 이용해 루트 노드로 변환
        if (root(e[i]._A, e[i]._B)) continue;
        // 두 트리를 연결한 뒤 루트를 명시하고 가중치를 ans에 더한다
        parent[e[i]._B] = e[i]._A;
        ans += e[i]._C;
    }

    // 최소 스패닝 트리의 가중치를 출력
    printf("%.2lf\n", ans);

    return 0;
}

- 프림 기법

#include <cmath>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

typedef pair<double, double> point;
typedef pair<double, int> edge; 

#define MAX_N 100
#define _y first
#define _x second
#define _cost first
#define _node second

// visit[i]: i번째 노드에 방문했다면 true, 아니라면 false
bool visit[MAX_N];
// 최소 스패닝 트리를 만들 그래프
vector<edge> graph[MAX_N];
// 프림 알고리즘에 사용할 우선순위 큐
priority_queue<edge, vector<edge>, greater<edge>> q;

// node번째 노드에 방문한 뒤 해당 노드에 연결된 에지를 q에 push
void push(int node) {
    // node번째 노드에 방문함을 표시한 뒤
    visit[node] = true;
    // 해당 노드에서 방문한 적 없는 노드로 연결되는 모든 에지를 q에 push
    for (edge e_ : graph[node]) if (!visit[e_._node]) q.push(e_);
}

int main() {
    // 최소 스패닝 트리의 가중치
    double ans = 0;
    // 노드의 개수
    int n;
    // 각 노드의 좌표
    point p[MAX_N];

    // 문제의 조건을 입력받은 뒤
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lf %lf", &(p[i]._y), &(p[i]._x));

    // 노드를 잇는 에지를 모두 만들어 graph에 저장
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        graph[i].push_back({sqrt(pow(p[i]._y - p[j]._y, 2) + pow(p[i]._x - p[j]._x, 2)), j});

    // 0번 노드에서 탐색을 시작
    push(0);

    // 방문한 적 있는 노드에 연결된 모든 에지에 대해
    while (!q.empty()) {
        // 가중치가 가장 작은 에지 하나를 가져온 뒤
        edge e = q.top();
        q.pop();

        // 현재 에지에 연결된 노드에 방문한 적 있다면 continue
        if (visit[e._node]) continue;
        // 현재 에지를 이용해 새로운 노드에 방문
        push(e._node);
        // 현재 에지의 가중치를 ans에 더한다
        ans += e._cost;
    }

    // 최소 스패닝 트리의 가중치를 출력
    printf("%.2lf\n", ans);

    return 0;
}