문제

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

이해

적군의 기지는 2차원 평면 상에 있으며 위치 정보와 반지름 정보가 주어진다. (x, y, r)

적군의 기지는 반지름만큼 통신범위를 가지고 만일 각 기지가 통신범위 안에 포함되면 서로 통신할 수 있다. 이를 연결되었다고 한다.

주어진 적군의 기지를 보고 연결된 독립적인 그룹의 개수를 세야한다.

접근

범위에 포함되면 같은 그룹으로 인식한다. 범위가 포함된다는 말은 두 원이 접하는 점이 1개 이상이라는 얘기이다. 이를 식으로 나타내면 다음과 같다.

distance <= r1 + r2

또한, 기지끼리는 서로 접하지 않아도 인접한 기지들에 의해 연결될 수 있다.

이러한 조건을 보면 union find 알고리즘을 활용하면 되겠다.

root 배열을 생성하고 경로 정보를 저장해야 한다. 경로 정보는 N이 3000 미만이기 때문에 N^2으로 처리해도 된다.

풀이

void makeSets(int n) {
    for (int i = 0; i < n; i++) {
        root[i] = i;
    }
}

int find(int n) {
    if (root[n] == n) {
        return n;
    } else {
        return root[n] = find(root[n]);
    }
}

void unite(int a, int b) {
    int aRoot = find(a);
    int bRoot = find(b);

    if (aRoot == bRoot) {
        return;
    }

    root[bRoot] = aRoot;
}

union find 코드이다. cpp의 경우 union 지시자를 쓸 수 없다. unite를 대신해서 사용했다.
find에서는 return할 때 경로 압축 기법을 활용했다.

bool circleTouch(int a, int b) {
    double distance = getDistance(a, b);
    double rSum = (double) nodes[a].r + nodes[b].r;

    if (distance > rSum) {
        return false;
    } else {
        return true;
    }
}

접하는지 여부를 판단하는 함수이다. 반지름의 합과 중심 사이의 거리를 활용했다.

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (find(i) == i ? 1 : 0);
        }
        cout << ans << endl;

마지막 출력부분이다. root 배열을 순회하면서 해당 인덱스의 root가 본인일 경우 (그룹 대장) 그룹의 개수를 카운트했다.

전체 코드

//boj10216

#include <iostream>

using namespace std;

class Node {
public:
    int x;
    int y;
    int r;
};

Node *nodes;
int *root;

void makeSets(int n) {
    for (int i = 0; i < n; i++) {
        root[i] = i;
    }
}

int find(int n) {
    if (root[n] == n) {
        return n;
    } else {
        return root[n] = find(root[n]);
    }
}

void unite(int a, int b) {
    int aRoot = find(a);
    int bRoot = find(b);

    if (aRoot == bRoot) {
        return;
    }

    root[bRoot] = aRoot;
}

double getDistance(int a, int b) {
    int dx = nodes[a].x - nodes[b].x;
    int dy = nodes[a].y - nodes[b].y;

    return sqrt(dx * dx + dy * dy);
}

bool circleTouch(int a, int b) {
    double distance = getDistance(a, b);
    double rSum = (double) nodes[a].r + nodes[b].r;

    if (distance > rSum) {
        return false;
    } else {
        return true;
    }
}

int main() {
    int T;
    cin >> T;

    while (T-- > 0) {
        int n;
        cin >> n;

        root = new int[n];
        nodes = new Node[n];

        makeSets(n);
        for (int i = 0; i < n; i++) {
            int x, y, r;
            cin >> x >> y >> r;

            nodes[i] = {x, y, r};
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (circleTouch(i, j)) {
                    unite(i, j);
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (find(i) == i ? 1 : 0);
        }
        cout << ans << endl;

        delete[] root;
        delete[] nodes;
    }
}

결과

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (root[i] == i ? 1 : 0);
        }
        cout << ans << endl;

초기 코드는 위처럼 직관적으로 root를 판단했는데 틀렸다고 나왔다. 대충 이유는 "경로 압축이 되지 않은 노드를 판단할 수 있어서" 였다.

경로 압축이 되지 않아도 누구에게 종속적이라면 본인이 아닌 다른 노드를 가리켜서 상관이 없는 줄 알았는데 이 부분을 수정하고 정답을 맞췄다.