10216번

10216번 - Count Circle Groups

결국 연결되는 그룹이 몇개인지를 알아내면 된다. 그래서 나는 유니온 파인드를 이용해서 값을 구했다.

주어진 n개의 통신기기들을 vector 에 저장하고, 2중 for문을 통해서 각각의 거리를 측정한다.

측정 거리가 서로의 반지름의 합보다 작거나 같으면, 두 지역은 연결할 수 있으므로

merge 를 이용해서 합해준다. 이때 find 함수값을 이용해 부모가 이미 같으면 굳이 다시 merge 할 필요가 없다.

나는 처음에 거리 r을 이차원 배열에서 위,아래,오른쪽,옆으로 생각해서 문제를 잘못 풀었고, 게다가 겹치지 않고 붙어있기만 해도 통신이 된

된다는 점을 제대로 못 읽어서 처음에 헤맸다. 문제를 다시 잘 읽는 습관을 들여야겠다.

<정답 코드>

#include<iostream>
#include<string.h>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
typedef struct {
    double x;
    double y;
    double r;
}antena;
int n, ans;
int p[3001];
vector<antena> v;
void init()
{
    ans = n;
    v.clear();
    
    for (int i = 0; i < 3001; i++)
    {
        p[i] = i;
    }
}
double dist(double x1, double y1, double x2, double y2)
{
    return sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
}
int find(int x)
{
    if (x == p[x])
    {
        return x;
    }
    else
    {
        return p[x] = find(p[x]);
    }
}
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
 
    if (x == y)
    {
        return ;
    }
    ans--;
    if (x > y)
    {
        swap(x, y);
    }
 
    p[y] = x;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        cin >> n;
        init();
        for (int i = 0; i < n; i++)
        {
            antena a;
            cin >> a.x >> a.y >> a.r;
            v.push_back(a);
        }
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i != j)
                {
                    double d1 = dist(v[i].x, v[i].y, v[j].x, v[j].y);
                    double d2 = v[i].r + v[j].r;
                    if (d1<=d2 && find(i)!=find(j))
                    {
                        merge(i, j);
                    }
                }
            }
        }
 
 
        cout << ans << "\n";
 
    }
 
    return 0;
}