[C++][백준 10216] Count Circle Groups

문제

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

접근 방법

그룹으로 묶는 문제입니다. 그룹은 유니온 파인드를 활용하여 묶어줄 수 있습니다. 직접 통신이 가능한지 여부는 거리 계산을 해주면 됩니다.

코드

#include <iostream>
#include <cstring>
using namespace std;

struct node
{
    int x, y, R;
};

int T, N;
int groupCnt;
node nodes[3000];
int group[3000];
bool isUsed[3000];

int find(int a)
{
    if (group[a] == a)
    {
        return a;
    }

    return group[a] = find(group[a]);
}

void merge(int a, int b)
{
    a = find(a);
    b = find(b);

    group[b] = a;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> T;

    while (T--)
    {
        cin >> N;

        for (int i = 0; i < N; ++i)
        {
            node &n = nodes[i];
            cin >> n.x >> n.y >> n.R;
            group[i] = i;
        }

        for (int i = 0; i < N; ++i)
        {
            const node &a = nodes[i];

            for (int j = i + 1; j < N; ++j)
            {
                const node &b = nodes[j];

                int dx = a.x - b.x;
                int dy = a.y - b.y;
                int dist = dx * dx + dy * dy;

                int rr = a.R + b.R;

                if (dist <= rr * rr)
                {
                    merge(i, j);
                }
            }
        }

        groupCnt = 0;

        memset(isUsed, false, sizeof(isUsed));

        for (int i = 0; i < N; ++i)
        {
            int j = find(i);

            if (isUsed[j])
            {
                continue;
            }

            isUsed[j] = true;
            ++groupCnt;
        }

        cout << groupCnt << "\n";
    }

    return 0;
}

풀이

각 통신영역에서 다음 통신영역에서부터 끝에 존재하는 통신영역까지 순회하며 통신영역 사이의 거리보다 R의 합이 더 큰지 확인해 봅니다. 만약 크다면 통신이 가능하다고 판단되므로 둘을 같은 그룹으로 묶어줍니다.

모든 통신영역을 살펴본 뒤 몇 개의 그룹이 존재하는지 확인해 주면 됩니다.