[백준 / C++] 10216번: Count Circle Groups

백준 10216번: Count Circle Groups
알고리즘 분류: 자료 구조, 그래프 이론, 그래프 탐색, 기하학, 분리 집합

백준 문제 바로가기

🤨 Hmm...

분리 집합 푸려고 고른 문젠데 기하학도 포함된 문제다.

근데 그냥 원이 만나는지만 판단하면 돼서 간단하다.

parent 배열 초기화 시켜놓고 두개 조합 골라서 원끼리 만나는지 확인하고 만나면 union 해주고 그룹 수-- 하면 된다.

끝!

💻 소스 코드

#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>
#define int long long
#define pii pair<int, int>
#define fastIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

typedef struct node {
    int x, y;
    int R;
    node(int x, int y, int R) {
        this->x = x;
        this->y = y;
        this->R = R;
    }
}NODE;

class BJ {
    int T;
    int N;
    int parent[3000];
    vector<NODE> location;
public:
    BJ();
    int findParent(int x);
    void unionParent(int x, int y);
};

BJ::BJ() {
    cin >> T;
    int x, y, R;
    while (T--) {
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> x >> y >> R;
            location.emplace_back(x, y, R);
            parent[i] = i;
        }

        int answer = N;
        for (int i = 0; i < N-1; i++) {
            for (int j = i+1; j < N; j++) {
                NODE c1 = location[i], c2 = location[j];
                int o1o2 = pow((double)(c2.x - c1.x), 2) + pow((double)(c2.y-c1.y), 2);
                int r1r2 = pow((double)(c1.R + c2.R),2);
                if (o1o2 <= r1r2 && findParent(i) != findParent(j)) {
                    unionParent(i, j);
                    answer--;
                }
            }
        }
        cout << answer << '\n';
        location.clear();
    }
}

int BJ::findParent(int x) {
    if (parent[x] == x)
        return x;
    parent[x] = findParent(parent[x]);
    return parent[x];
}
void BJ::unionParent(int x, int y) {
    int px = findParent(x);
    int py = findParent(y);
    if (px <= py)
        parent[py] = parent[px];
    else
        parent[px] = parent[py];
}

signed main(){
    fastIO;

    BJ Q10216;
}