[ 백준 ] 10216 / Count Circle Groups

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
212/228
post-thumbnail

# Appreciation

/*
 * Problem :: 10216 / Count Circle Groups
 *
 * Kind :: Union Find
 *
 * Insight
 * - 상호간에 통신이 가능한 진영끼리는 결집력 있는 한 그룹처럼 행동한다
 *   적군 진영의 그룹 개수를 알아내야 한다
 *   + 그룹 내부의 진영끼리는 통신이 가능하다, 그룹 간에는 서로 통신이 불가능하다
 *     # Disjoint Set(서로소 집합)의 개수를 구해야 한다
 *       진영끼리 연락되면 같은 그룹에 속하고
 *       그렇지 않다면 서로 다른 그룹에 속한다
 *       -> Union Find 알고리즘을 적용하자
 *
 * Point
 * - DFS 로도 BFS 로도 풀 수 있다
 *   + 다만, 다음 노드를 탐색할 때 연결되었는지 그렇지 않은지 매번 확인하기보다는
 *     아예 배열을 따로 만들어서 처음에 각 진영끼리의 연결여부를 확인해주면
 *     훨 효율적으로 탐색할 수 있다
 *     # 사실 처음 불때는 위와같은 아이디어로 BFS 로 풀었는데
 *       Union Find 가 훨씬 더 빠를 것 같아서 이번에는 그렇게 풀어보았다
 *       -> 그런데 BFS 가 더빠르네...?!?
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N;
struct Camp { int x, y, r; };
Camp C[3000];
int P[3000];
int R[3000];

// Set up : Functions Declaration
bool isConnected(int u, int v);
int find(int u);
void merge(int u, int v);

int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int T; cin >> T;

    while (T--) {
        cin >> N;
        for (int i=0; i<N; i++) {
            int x, y, r;
            cin >> x >> y >> r;
            C[i] = {x, y, r};
        }

        // Process
        /* P[i] = i 번째 진영의 부모 노드, R[i] = i 번째 진영의 랭크 */
        for (int i=0; i<N; i++) {
            P[i] = i;
            R[i] = 1;
        }

        int ans = N; /* 초기에는 각각의 진영를 하나의 그룹으로 간주 */
        for (int i=0; i<N; i++) {
            for (int j=i+1; j<N; j++) {
                if (find(i) != find(j)) { /* i 번째 진영와 j 번째 진영의 부모 노드가
                                           * 서로 다르다면 */
                    if (isConnected(i, j)) { /* i 번째 진영와 j 번째 진영이
                                              * 통신이 가능하다면 */
                        merge(i, j); /* i 번째 진영와 j 번째 진영은 같은 그룹에 속함 */
                        ans--; /* 두 그룹이 하나의 그룹으로 통합되었으므로
                                * 전체 그룹의 개수 감소 */
                    }
                }
            }
        }

        // Control : Output
        cout << ans << endl;
    }
}

// Helper Functions
bool isConnected(int u, int v)
/* u 번째 진영와 v 번째 진영가 통신가능하다면 true 를 반환, 그 외 false 를 반환 */
{
    Camp cu = C[u];
    Camp cv = C[v];
    int dy = cv.y - cu.y;
    int dx = cv.x - cu.x;
    int ru = cu.r;
    int rv = cv.r;
    /* 통신이 가능하려면 두 진영의 좌표간의 거리의 제곱이
     * 두 진영의 반지름의 합의 제곱보다 같거나 작아야 함 */
    return dy*dy + dx*dx <= (ru+rv)*(ru+rv);
}

int find(int u)
/* u 번째 진영의 부모 노드를 반환 */
{
    if (P[u] == u) return u;
    return P[u] = find(P[u]); /* 경로 최적화 */
}

void merge(int u, int v)
/* u 번째 진영와 v 번째 진영가 속한 그룹을 하나로 통합 */
{
    int pu = find(u); /* u 번째 진영의 부모 노드 */
    int pv = find(v); /* v 번째 진영의 부모 노드 */

    /* pu 의 랭크가 항상 pv 의 랭크보다 같거나 크도록 함 */
    if (R[pu] < R[pv]) {
        swap(pu, pv);
    }

    /* pv 의 부모 노드를 pu 로 변경
     * 이로써, u 번째 진영가 속한 그룹과 v 번째 진영가 속한 그룹이 하나로 통합됨 */
    P[pv] = pu;
    if (R[pu] == R[pv]) { /* pu 그룹과 pv 그룹의 랭크가 서로 같다면 */
        R[pu]++; /* pu 그룹의 랭크 증가 */
    }
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글