[10216] Count Circle Groups

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

처음에 단순히 dfs로 해결했습니다.

간단하지만 런타임 시간이 꽤 오래 걸리더군요.

일단 다 풀고나서 다른 분들이 어떻게 풀었나 봤더니

disjoint-set(union-find)로 푸셨더라구요!

그래서 저도 다시 풀어보았습니다.

간단했습니다. 우선 연결되어있다면 union을 해서 같은 그룹으로 묶습니다.

union을 한다고 모든 노드에서의 부모가 바뀌는 것은 아닙니다.

x와 y를 유니온 하면 x와 y의 부모만 바뀌는 것이므로

다시한번 find를 해줘야 완전히 갱신이 됩니다.

아무튼!! 이것은 union-find에 대해서 공부하시면 알게되실겁니다.

그리고 나서 모든 노드에 대해 그루핑이 끝났다면!

그룹이 몇개인지 세어줘야합니다!

저는 간단하게 노드 3천개에 대한 tmp 배열을 만들어서

해당 노드의 부모가 tmp배열에서 true라면 이미 센 그룹이므로 넘어가고 

false라면 안센 그룹이므로 tmp배열을 갱신시켜주고

그룹의 개수를 늘려줍니다.

uinon-find 코드입니다.

#include <iostream>
#include <string.h>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
pii pos[3000];
int r[3000];
 
int parent[3000];
int n;
 
bool isConneted(int a, int b) {
    int x = pos[a].first - pos[b].first;
    int y = pos[a].second - pos[b].second;
    int z = r[a] + r[b];
 
    return (x * x + y * y) <= z * z;
}
 
int Find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = Find(parent[x]);
}
 
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
 
    if (x != y) {
        parent[x] = y;
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        cin >> n;
 
        for (int i = 0; i < n; i++) parent[i] = i;
        
        for (int i = 0; i < n; i++) {
            cin >> pos[i].first >> pos[i].second >> r[i];
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (isConneted(i, j) && parent[i] != parent[j]) {
                    Union(i, j);
                }
            }
        }
 
        bool tmp[3000] = { 0, };
        int ret = 0;
 
        for (int i = 0; i < n; i++) {
            int p = Find(i);
            if (!tmp[p]) {
                tmp[p] = 1;
                ret++;
            }
        }
 
        cout << ret << '\n';
    }
 
    return 0;
}

dfs코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
pii pos[3000];
int r[3000];
bool visit[3000];
int n;
 
int calcDistance(pii a, pii b) {
    int  x = (a.first - b.first);
    int y = (a.second - b.second);
    return x * x + y * y;
}
 
void dfs(int idx) {
    for (int i = 0; i < n; i++) {
        int rSum = r[idx] + r[i];
        if (idx == i || visit[i] || calcDistance(pos[idx], pos[i]) > rSum * rSum) continue;
        visit[i] = 1;
        dfs(i);
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(visit, 0, sizeof(visit));
 
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            cin >> pos[i].first >> pos[i].second >> r[i];
        }
 
        int ret = 0;
 
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                dfs(i);
                ret++;
            }
                
        }
        cout << ret << '\n';
    }
 
    return 0;
}