[BOJ-10216]Count Circle Groups

원이 A, B가 있을 때 

경우 1) 원이 접하거나, 겹치는 경우에는 한 그룹이라고 본다. 

경우 2) 원이 접하지않고, 겹치는 경우는 두 그룹이라고 본다.

하지만 원이 A, B, C 가 있으며, A 와 C 를 서로 맞닿아있는 B가 있는 경우 A, B, C 는 한 그룹으로 본다. 

이때 입력에 대해 그룹 수를 구하는 것이 이 문제 요약이다.

일단 이 문제 분류가.. DFS/BFS 이어서 풀어보려 했는데 왜 생각을 해봐도 DFS BFS로 생각이 안나는지.. 

그래서 Union Find로 풀었다. 

맞닿아 있는 경우에는 경우 1이기때문에 루트를 합쳐준다. 

맞닿아 있지 않은 경우2는 그냥 냅둔다.

그리고 무조건 (x, y, r) = (x좌표, y좌표, 반지름) 이고, 이 모든 입력은 정수로 주어지기 때문에 굳이 double.... 소수점 자료형을 쓰지 않아도 문제를 풀 수가 있다. 

 

원 A, B 거리를 루트를 씌우지 않은 값과 원A, B의 반지름을 더하고, 제곱한 값을 비교해주면 정수만 나오기 때문에 연산시간을 줄일 수 있다. 

#include<cstdio>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct point {
    int x, y, r, root;
    point(int ix, int iy, int ir) : x(ix), y(iy), r(ir) {
        root = -1;
    }
};
const int MAX = 3000;
vector<point> input;
int ROOT[MAX];
vector<int> res;
//typedef long double lf; // 모든 입력이 정수이므로 필요없음.
 
int pow2(int a) {
    return a*a;
}
int distance(point a, point b) {
    return pow2(b.x - a.x) + pow2(b.y - a.y);
}
int distance_search(int r, int dist) {
    int RAD = r*r;
    return (RAD >= dist) ? true : false;
}
void init() {
    input.clear();
    for (int i = 0; i < MAX; i++) ROOT[i] = -1;
    return;
}
 
int find(int sub) {
    if (ROOT[sub] == -1) return sub;
    else return find(ROOT[sub]);
}
bool isUnion(int u, int v) {
    return find(u) == find(v);
}
int union_find(int u, int v) {
    if (!isUnion(u, v)) {
        int root_u = find(u);
        int root_v = find(v);
 
        if (root_u < root_v) ROOT[root_v] = root_u;
        else if (root_v < root_u) ROOT[root_u] = root_v;
        return true; 
    }
    return false;
}
 
int main() {
    int T; scanf("%d", &T);
    for (int tc = 0; tc < T; tc++) {
        int n; scanf("%d", &n);
        init();
        for (int i = 0; i < n; i++) {
            int x, y, r;
            scanf("%d%d%d", &x, &y, &r);
            input.push_back(point(x, y, r));
        } // input data
 
        for (int i = 1; i < n; i++) {
            point& here = input[i];
 
            for (int ti = 0; ti < i; ti++) {
                point& there = input[ti];
                if (distance_search(here.r + there.r, distance(here, there))) {
                    union_find(i, ti);
                }
            }// 0~i-1 == i
        }
 
        //for (int i = 0; i < n; i++) printf("index[ %d ] : root - %d \n",i, ROOT[i]);
        int ans = 0;
        for (int i = 0; i < n; i++) if (ROOT[i] == -1) ans++;
        printf("%d\n", ans);
    }
    return 0;
}
 
//1
//6
//0 0 1
//10 0 1
//4 0 1
//6 0 1
//2 0 1
//8 0 1
 

03:35-03:54

DFS 로 좀 더 생각하니 풀리긴 했는데, 처음에 시간 초과할 것 같아서 이렇게 짜면 안될 것 같다고 생각했는데 1.5초 정도 걸렸다. union-find로 풀었을 때는 0.7초 정도 걸렸다. 

우선, DFS 로 풀이하는 방법은 원의 집합 루트가 정해져 있지 않은 경우, root를 지정한다. 

root 가 지정되어 있다면 DFS를 하지 않는다. 

root 가 지정되어 있지않다면 DFS를 한다. 

가지치기 + 완전탐색

#include<cstdio>
#include<vector>
#include<algorithm>
 
using namespace std;
 
const int NONE = 11111;
struct point {
    int x, y, r, root;
    point(int ix, int iy, int ir) : x(ix), y(iy), r(ir) {
        root = NONE;
    }
};
const int MAX = 3000;
vector<point> input;
int ROOT[MAX]; // 필요없음
vector<int> res; // 필요없음
int n;
//typedef long double lf; // 모든 입력이 정수이므로 필요없음.
 
int pow2(int a) {
    return a*a;
}
int distance(point a, point b) {
    return pow2(b.x - a.x) + pow2(b.y - a.y);
}
int distance_search(int r, int dist) {
    int RAD = r*r;
    return (RAD >= dist) ? true : false;
}
void init() {
    input.clear();
    //for (int i = 0; i < MAX; i++) ROOT[i] = -1;
    return;
}
 
void dfs(int u) {    
    for (int i = 0; i < input.size(); i++) {
        if (input[i].root != NONE || i == u) continue;
        if ( distance_search( input[u].r + input[i].r, distance( input[u], input[i] ) ) ) {
            input[u].root = input[i].root = (input[u].root < input[i].root) ? input[u].root : input[i].root;
            dfs(i);
        }
    }
    return;
}
 
 
int main() {
    int T; scanf("%d", &T);
    for (int tc = 0; tc < T; tc++) {
        scanf("%d", &n);
        init();
        for (int i = 0; i < n; i++) {
            int x, y, r;
            scanf("%d%d%d", &x, &y, &r); 
            input.push_back(point(x, y, r));
        } // input data
 
        int root = 0;
        for (int i = 0; i < n; i++) {
            if (input[i].root == NONE) {
                input[i].root = ++root;
                dfs(i);
            }            
        }
        
        printf("%d\n", root);
    }
    return 0;
}
 
//1
//6
//0 0 1
//10 0 1
//4 0 1
//6 0 1
//2 0 1
//8 0 1