[BOJ/백준][Gold5] 10216 : Count Circle Groups (C++)

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

10216번: Count Circle Groups

 

 

[난이도] Gold5
[유형] union find

[풀이]
union find를 이용해서 서로 접근 가능한 점들을 한 그룹으로 묶어준다. N이 3000이므로 N^2으로 해결이 가능하다.

 

#include <cstdio>
#include <cstring>
using namespace std;
struct P{
    int x,y,r;
};
int T,N,uf[3000];
bool check[3000];
P a[3000];
int find(int n){
    if(uf[n]==n) return n;
    return find(uf[n]);
}
void merge(int n,int m){
    n=find(n);
    m=find(m);
    uf[n] = m;
}
int adj(int i,int j){
    int d = (a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
    return d <= (a[i].r+a[j].r)*(a[i].r+a[j].r);
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);

        for(int i=0;i<N;i++) uf[i]=i;

        for(int i=0;i<N-1;i++){
            for(int j=i+1;j<N;j++){
                if(adj(i,j)) merge(i,j);
            }
        }

        memset(check,0,sizeof(check));
        int ans=0;
        for(int i=0;i<N;i++){
            int p = find(i);
            if(!check[p]){
                ans++;
                check[p]=1;
            }
        }
        printf("%d\n",ans);
    }
} 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/10216.cpp