(BOJ) 10216 풀이

#include<bits/stdc++.h>

using namespace std;

typedef struct xyr{
    int x,y,r;
}xyr;

xyr cord[5001];
int visited[5001];
int sqare(int x){
    return x*x;
}
int main(void){
    int T,N,ans=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        ans=0;
        fill(visited,visited+N,0);
        stack<int> s;
        for(int i=0;i<N;i++){
            scanf("%d%d%d",&cord[i].x,&cord[i].y,&cord[i].r);
        }
        for(int i=0;i<N;i++){
            if(visited[i])continue;
            visited[i]=1;
            s.push(i);
            ans++;
            // printf("(%d,%d,%d) -> ",cord[i].x,cord[i].y,cord[i].r);
            while(!s.empty()){
                int v=s.top();
                s.pop();
                for(int j=0;j<N;j++){
                    if(!visited[j] && sqare(cord[v].x-cord[j].x)+sqare(cord[v].y-cord[j].y) <= sqare(cord[v].r+cord[j].r)){
                        // printf("(%d) (%d,%d,%d) -> ",sqare(cord[i].x-cord[j].x)+sqare(cord[i].y-cord[j].y),cord[j].x,cord[j].y,cord[j].r);
                        visited[j]=1;
                        s.push(j);
                    }
                }
            }
            // printf("\n");

        }
        printf("%d\n",ans);
    }
}

이번문제는 다른코드 참고해서 공부했다.

먼저, DFS,BFS 관련문제 풀고있다가 이거는 유니온 파인드로 풀 수 있다고해서

유니온 파인드로 풀다가, BFS DFS 로 풀고싶어서 다른코드 참고했다. (https://blog.encrypted.gg/146)

 

유니온 파인드로 풀면, 먼저 초기값 ans 를 N 으로 설정하고

반복문을 N^2 만큼 돌면서 ( i==j 는 제외 )

거리조건을 만족하면, 각각의 루트노드를 찾고 부모가 다르면 ans 값을 감소시키고 합집합 연산을 한다.

 

위 코드는 DFS 인데,

첫번째 반복문에서 좌표값을 차례대로 가져오며 ans 를 증가시킨다.

다른 좌표들에 대해 거리조건을 만족하면 스택에 push 하고 DFS 실시한다.

그러면 유니온파인드 알고리즘처럼 연결된 구역들에 대해서는 visited 처리가 되어 첫번째 반복문에서는 visited 처리가 되지 않은 좌표를 찾을 떄까지 continue 하는 식으로 모든 구역들을 찾을 수 있다.