BOJ 10216 - Count Circle Groups(C++)

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

10216번: Count Circle Groups

풀이

노드별 거리 비교를 위한 2중 for문

통신 가능 확인 (p1.x-p2.x)² + (p1.y-p2.y)² <= (r1+r2)² 

통신가능 지역이라면 merge(작은값이 부모가 되도록, 2개의 노드가 합쳐지므로 ans--)

 

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

int T, N;
struct Point {
    int y, x, r;
};
Point point[3001];
int parent[3001];

int find(int now) {
    if (now == parent[now])return now;
    return parent[now] = find(parent[now]);
}

bool check(int i, int j) {//통신영역 확인
    Point p1 = point[i];
    Point p2 = point[j];
    
    return pow(p1.y - p2.y, 2) + pow(p1.x - p2.x, 2) <= pow(p1.r + p2.r, 2);
}

void merge(int i, int j) {
    int pi = find(i);
    int pj = find(j);
    if (pj < pi)
        swap(pi, pj);
    parent[pj] = pi;
}

int main() {
    cin >> T;

    for (int _ = 0; _ < T; _++) {//테스트 케이스 수
        cin >> N;
        int ans = N;
        int X, Y, R;
        memset(parent, -1, sizeof(parent));

        for (int idx = 0; idx < N; idx++) {//진영의 수
            cin >> X >> Y >> R;
            point[idx] = { Y,X,R };
            parent[idx] = idx;
        }

        for (int i = 0; i < N-1; i++) {//union find
            for (int j = i+1; j < N; j++) {
                if (find(i) == find(j))continue;
                if (check(i, j)) {
                    merge(i, j);
                    ans--;
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}