BOJ 10216 - Count Circle Groups(유니온 파인드, 서로소 집합)

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

10216번: Count Circle Groups

- 문제에서 주어진 조건에 따라 노드가 연결되었는지를 체크하는 함수, 연결되었다면 union 연산을 통해서 같은 집합임을 체크해준다. 

- 이 문제에서 찾을 수 반례로 

1
3
0 0 1
2 2 1
0 2 1

가 있다. 처음 두 노드는 연결이 안되어있는데 그 사이에 0,2 노드가 생기면서 모두 같은 집합이 되는 그런 케이스이다. 

그래서 모든 노드를 n번 검사하는 On^2 방식으로 풀었다. 징검다리식으로 부모가 점점 바뀌더라도 결국 모든 노드를 n번 검사하게 되면1~n이 모두 길이n의 편향트리 처럼 연결되 있는 극단적인 구조에서도 노드n의 부모(부모가 같으면 같은 집합)는 1임이 분명하기 때문이다

- union, find 연산을 템플릿처럼 저장해놨다가 필요할 때 약간씩 변형해서 쓴다. 문제에서는 모든 집합의 갯수를 구해야하므로 가능한 답의 최대값은 노드의 갯수이고 union연산이 일어날때마다 1씩 빼주면 된다.

#include <cmath>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;
#define union _union
#define endl '\n'
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)

int parent[3001];
tuple<int, int, int> enemy[3001];
int ans;

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

void union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;

    --ans;
    if (a < b)
        parent[b] = a;
    else
        parent[a] = b;
}

bool isConnected(int a, int b) {
    const auto& [x1, y1, r1] = enemy[a];
    const auto& [x2, y2, r2] = enemy[b];

    if (pow(r1 + r2, 2) >= pow(x1 - x2, 2) + pow(y1 - y2, 2)) return true;
    return false;
}

int t;
int main() {
    FASTIO;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        ans = n;

        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
        }

        for (int i = 1; i <= n; ++i) {
            int x, y, r;
            cin >> x >> y >> r;
            enemy[i] = {x, y, r};
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i == j) continue;
                if (isConnected(i, j)) {
                    union(i, j);
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}