BOJ)10216 Count Circle Groups

문제: icpc.me/10216

N개의 진영이 주어 질 때 각 진영이 통신영역이 닿거나 겹치는 부분이 있으면 서로 통신이 가능하다. 그리고 직접적으로 통신이 불가능 하더라도 중간에 몇개의 통신을 거쳐서 통신이 가능하다면 i와 j는 통신이 가능하다고 본다.

통신이 서로 가능한 진영들을 그룹으로 묶을 때 그룹의 수를 출력하는 문제이다.

우리는 a와b가 통신이 가능하고 b와c가 통신이 가능하면 a와c가 통신이 가능한 그룹이 된다는 사실을 가지고 disjoint set을 통하여 문제를 해결할 수 있다.

N이 3000밖에 되지 않으므로

N^2의 방법으로 각 진영들을 비교하여 같은 그룹이 아닌 그룹들중에서 통신영역이 겹치는 두 그룹을 union 시켜주면서 시켜줄때마다 그룹의 수를 하나씩 차감시키는 방법으로 답을 구할 수 있다.

#include <cstdio>
#include <algorithm>
#define MAX_N 3000
using namespace std;
int t, n, x, y, r, par[MAX_N + 1], ans;
pair<pair<int, int>, int> a[MAX_N + 1];
void init() {
    for (int i = 1; i <= n; i++)
        par[i] = i;
}
int find(int v) {
    if (par[v] == v)return v;
    return par[v] = find(par[v]);
}
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)return;
    ans--;
    par[x] = y;
}
double dist(pair<int,int> x, pair<int,int> y) {
    return sqrt((x.first - y.first)*(x.first - y.first) + (x.second - y.second)*(x.second - y.second));
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d", &x, &y, &r);
            a[i] = { {x,y},r };
        }
        init();
        ans = n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    continue;
                double d = dist(a[i].first, a[j].first);
                if (d <= (double)(a[i].second + a[j].second))
                    merge(i, j);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}