[PS] 백준 10216번: Count Circle Groups

|

문제

내가 이해한 문제 내용

2차원 좌표평면에 각 좌표와 반지름이 주어질 때 닿거나 겹치는 것을 그룹화한다. 이 때 다른 원을 거쳐서 또 다른 원으로 갈 수 있으면 그것도 한 그룹이 된다. 그룹의 수를 구하시오.

접근 방식

현재 원부터 이전 원들을 검사하면서 닿거나 겹치는 것을 유니온-파인드로 합친다.

어려웠던 점 & 배운 점

유니온 연산을 구현하는 것을 까먹어서 다시 봤고 설마 $O(N^2)​$ 풀이이겠어 하는 방심을 했다;; 아 또 전역변수 초기화에서 실수를 해서 맞을 걸 계속 틀렸다 ㅠ

시간복잡도

$O(N^2 \alpha(N))$

코드

#include <cstdio>
#include <algorithm>

struct enemy{
    int x;
    int y;
    int r;

    bool operator<(const enemy& e) const{
        return x<e.x;
    }
};

enemy g[3001];
int tc,n;
int p[3001],r[3001],num[3001];

inline int dist(int x1, int y1, int x2, int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

int find(int v)
{
    if(v==p[v]) return v;
    else return p[v] = find(p[v]);
}

void uni(int v1, int v2)
{
    v1 = find(v1);
    v2 = find(v2);

    if(r[v1]>r[v2]) p[v2]=v1;
    else p[v1]=v2;
    if(r[v1]==r[v2]) r[v2]++;
}

int main(void)
{
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].r);

        std::sort(g+1,g+n+1);

        for(int i=1; i<=n; i++){
            p[i] = i;
            r[i] = 0;
        }

        for(int i=2; i<=n; i++){
            for(int j=1; j<i; j++){
                if(find(i) != find(j) &&
                    dist(g[i].x,g[i].y,g[j].x,g[j].y)<=(g[i].r+g[j].r)*(g[i].r+g[j].r))
                    uni(i,j);
            }
        }

        int ans = 0;
        for(int i=1; i<=n; i++) num[find(i)] = 1;
        for(int i=1; i<=n; i++) {
            if(num[i]) ans++;
            num[i] = 0;
        }
        printf("%d\n",ans);
    }
    return 0;
}