백준10216 Count Circle Groups

작성일 | In

문제 링크

  • http://icpc.me/10216

문제 출처

  • 2014 Coder’s High C번

사용 알고리즘

  • DFS

시간복잡도

  • O(n2)

풀이

어떤 두 진영의 통신영역이 서로 겹치거나 닿는 부분이 있다면, 두 진영은 직접적으로 통신할 수 있습니다. 직접적으로 통신이 가능한 지역들을 한 그룹으로 묶었을 때, 몇 개의 그룹으로 나뉘게 되는지 구하는 문제입니다.

이 문제는 연결 요소의 개수를 구하는 문제로 바꿔 풀 수 있습니다. 각 진영을 정점으로 잡고, 직접적으로 통신을 할 수 있는 진영(정점)들을 간선으로 이어준 뒤, 해당 그래프에서 DFS나 BFS를 돌려 연결 요소의 개수를 찾으면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

typedef double d;

int t;

struct asdf{
	d x, y, r;
};

void bfs(vector<int> g[3010], bool chk[3010], int start, int &cnt){
	queue<int> q;
	q.push(start);
	chk[start] = 1;
	cnt++;
	while(!q.empty()){
		int poped = q.front();
		q.pop();
		for(int i=0; i<g[poped].size(); i++){
			int next = g[poped][i];
			if(!chk[next]){
				q.push(next);
				chk[next] = 1;
				cnt++;
			}
		}
	}
}

void process(){
	int n; scanf("%d", &n);
	asdf arr[3010] = {0};
	bool chk[3010] = {0};
	int cnt = 0;
	int ans = 0;
	//input
	for(int i=0; i<n; i++){
		scanf("%lf %lf %lf", &arr[i].x, &arr[i].y, &arr[i].r);
	}

	//make_graph
	vector<int> g[3010];
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(i == j) continue;
			d xx = arr[i].x - arr[j].x;
			d yy = arr[i].y - arr[j].y;
			d dist = sqrt(xx*xx + yy*yy);
			d r = arr[i].r + arr[j].r;
			if(dist <= r) g[i].push_back(j);
		}
	}

	//bfs
	while(cnt < n){
		for(int i=0; i<n; i++){
			if(!chk[i]){
				bfs(g, chk, i, cnt);
				ans++;
			}
		}
	}
	printf("%d\n", ans);
}

int main(){
	scanf("%d", &t);
	while(t--){
		process();
	}
}