[C++] 1774 - 우주신과의 교감 (골드 3)

1. 문제 설명

 

1774번: 우주신과의 교감

 

---

2. 아이디어

 

💡 사이클을 이루지 않는 최소 비용의 간선 찾기 => MST

보자마자 최소 신장 트리를 만들어야 겠다는 건 떠올리지 못 했고,

한참을 문제를 째려보다가 탐욕법으로 접근하면 되겠다 싶긴 했는데 구현이 막혔다.

(각 노드가 선택할 수 있는 경로 중에 가장 비용이 작은 간선을 선택하면 되므로 탐욕법 접근이 가능하다 판단했다.)

 

구현이 막혔던 이유는 처음에 모든 정점의 좌표를 이용해서 간선에 대한 비용을 계산해두고,

문제에서 제공해준 "이미 선택된 간선"을 어떻게 처리할 지 난감했다.

하려면 할 수 있겠지만, 시간 복잡도 계산이 불가능할 정도의 복잡함.

 

애초에 최소 스패닝 알고리즘 문제를 풀어본 적이 없어서 이 참에 찾아봤다.

Kruscal MST 알고리즘을 사용해서 MST를 만들 수 있다는데, 이게 결국 탐욕법 + Union Find를 사용하는 방법이었다.

 

아이디어만 얻었더니 바로 풀긴 했으나,

여기서 Union Find를 사용해보겠다는 생각을 못 했다는 게 좀 자존심 상했다.

심지어 아이디어를 다른 곳에서 얻었음에도 구현하는 데 시간 제법 많이 걸렸다. 

요새 문제 너무 안 푼 티가 나나..

 

1️⃣ 모든 정점 연결

void init() {
    cin >> n >> m;
    for (int i=0, x, y; i<n; ++i) {
        cin >> x >> y;
        godCoords.push_back({y, x});
    }

    for (int i=0; i<=n; ++i) parent[i] = i;
    for (int i=0, u, v; i<m; ++i) {
        cin >> u >> v;
        unionParent(u-1, v-1);
    }

    for (int i=0; i<n; ++i) for (int j=i+1; j<n; ++j) {
        if (cmpParent(i, j)) continue;
        edges.push_back({i, j, calcDist(godCoords[i], godCoords[j])});
    }
}

좌표를 우선 모두 입력받고, 이미 이어진 정점에 대해서는 union find로 연결 정보를 갱신한다.

 

하나라도 이어진 간선이 있다면, 문제 조건에 의해 다른 간선이 이어질 일은 없다.

즉, 순환 구간이 생길 일이 절대 없는 서로소 관계이므로 union find를 사용해도 무방하다.

 

이미 연결된 간선에 대해서는 비용 계산이 필요 없으므로,

모든 정점을 서로 연결해주고 비용을 계산하여 edges에 저장한다.

 

2️⃣ edges 정렬

sort(edges.begin(), edges.end(), cmp);

사실 여기서 시간 초과가 나지 않을까 심히 염려스러웠다.

그런데 최악의 경우 N = 1,000이고 M=1이었는데, M=0이라고 가정해도 edges 원소 개수는 ∑x (1 <= n <= 100)이므로 101 * 500 = 500,500 

sort 함수는 O(N*lgN)이니까 충분하다고 판단했다.

 

이렇게 하면 가장 작은 비용을 가진 간선들이 모두 앞으로 모이게 된다.

 

3️⃣ MST 만들기

ld makeMST() {
    ld answer = 0;

    for (Edge edge : edges) {
        if (cmpParent(edge.u, edge.v)) continue;

        answer += edge.w;
        unionParent(edge.u, edge.v);
    }

    return answer;
}

여긴 진짜 간단하다.

edges를 순회하면서, 이미 연결된 정점이면 무시한다. (여기서 기존에 연결된 간선이 갱신될 일도 없어진다.)

 

만약, 아직 연결되지 않은 정점이 나온 경우 바로 연결한다.

어차피 가장 최소 비용을 가지는 간선임이 자명하므로 문제 없다.

끝나면 바로 union 해버리자.

 

---

3. 코드

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

#define INF 2147483647

using namespace std;

typedef pair<int, int> pii;
typedef long double ld;
typedef struct Edge {
    int u, v;
    ld w;
} Edge;

int n, m;
vector<Edge> edges; 
vector<pii> godCoords;
int parent[1001];

void init();
int findParent(int);
void unionParent(int, int);
bool cmpParent(int, int);
ld makeMST();
ld calcDist(pii a, pii b) {
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}
bool cmp(Edge &a, Edge &b) {
    return a.w < b.w; 
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.precision(2); cout.setf(ios::fixed);
    init();
    sort(edges.begin(), edges.end(), cmp);

    cout << makeMST() << "\n";
    
    return 0;
}

void init() {
    cin >> n >> m;
    for (int i=0, x, y; i<n; ++i) {
        cin >> x >> y;
        godCoords.push_back({y, x});
    }

    for (int i=0; i<=n; ++i) parent[i] = i;
    for (int i=0, u, v; i<m; ++i) {
        cin >> u >> v;
        unionParent(u-1, v-1);
    }

    for (int i=0; i<n; ++i) for (int j=i+1; j<n; ++j) {
        if (cmpParent(i, j)) continue;
        edges.push_back({i, j, calcDist(godCoords[i], godCoords[j])});
    }
}

int findParent(int node) {
    if (parent[node] == node) return node;
    return parent[node] = findParent(parent[node]);
}

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

bool cmpParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    return (a == b) ? true : false;
}

ld makeMST() {
    ld answer = 0;

    for (Edge edge : edges) {
        if (cmpParent(edge.u, edge.v)) continue;

        answer += edge.w;
        unionParent(edge.u, edge.v);
    }

    return answer;
}