백준) 10216 Count Circle Groups

Count Circle Groups

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

1. 접근

캠프들 끼리는 통신영역에 따라 한 그룹이 될 수도 안될 수도 있다.

그래프에서 총 그룹은 몇개나 나올까?

그래프는 n^2 에 만들 수 있을 것이다. 서로서로 비교해가면서 간선을 만들어준다.

그러고 나면 그래프에서 그룹이 총 몇개 있는지 찾는 법은 디스조인트-셋 이나 BFS / DFS 로 조질 수 있다.

2-1) 풀이 1

그래프에 대해 DFS로 그룹이 몇 개 있는지 셀 수 있을 것이다. 

visit을 확인해가면서 모든 캠프에 대해 DFS()를 호출해버린다.

간선이 N^2 개니까, 따라서 모든 캠프 N * DFS의 시간복잡도 (N + N^2) -> N^3 이나 걸린다.

2-2) 코드

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
using namespace std;
 
int t, n;
int camp[3000][3];
int visit[3000];
vector<vector<int>> map;
 
int dfs(int x) {
    int cnt = 1;
    visit[x] = 1;
 
    for (auto a : map[x]) {
        if (visit[a])
            continue;
        cnt += dfs(a);
    }
    return cnt;
}
 
int main() {
    scanf("%d", &t);
    while (t--) {
        map.clear();
        memset(visit, 0, sizeof(visit));
 
        scanf("%d", &n);
        map.resize(n);
 
        for (int i = 0; i < n; ++i)
            scanf("%d %d %d", &camp[i][0], &camp[i][1], &camp[i][2]);
 
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int x = camp[i][0] - camp[j][0];
                int y = camp[i][1] - camp[j][1];
                double r = (double)camp[i][2] + (double)camp[j][2];
                double d = sqrt(x*x + y*y);
 
                if (d <= r) {
                    map[i].push_back(j);
                    map[j].push_back(i);
                }
            }
        }
 
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (visit[i])
                continue;
 
            cnt++;
            for (auto v : map[i])
                dfs(v);
        }
 
        printf("%d\n", cnt);
    }
    return 0;
}

3-1) 풀이 2

사실 집합이 몇개나 생기는지 세기만 하면 된다. 집합에 몇개나 들어있는지 알 필요가 없다

그러면 각 노드에 대해 그래프를 만들면서 동시에 두 노드간 부모가 다르면(find) 집합을 만들어 버릴 수 있다.(merge)

처음의 각 노드가 하나의 집합이었다면, merge를 할 수록 집합 갯수는 줄어든다.

디스조인트 셋은 선형시간에 연산하므로 이 방법은 N^2 이다.

3-2) 코드

#include <stdio.h>
#include <math.h>
using namespace std;
 
int t, n;
int camp[3000][3];
int parent[3000];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
 
void merge(int x, int y) {
    x = find(x);
    y = find(y);
 
    if (x == y)
        return;
    else
        parent[x] = y;
}
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d %d %d", &camp[i][0], &camp[i][1], &camp[i][2]);
            parent[i] = i;
        }
            
        int cnt = n;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int x = camp[i][0] - camp[j][0];
                int y = camp[i][1] - camp[j][1];
                int r = camp[i][2] + camp[j][2];
                int d = x*x + y*y;
 
                if (d <= r * r) {
                    if (find(i) != find(j)) {
                        merge(i, j);
                        cnt--;
                    }
                }
            }
        }
 
        printf("%d\n", cnt);
    }
    return 0;
}