백준 10216 Count Circle Groups

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 좌표와 반지름을 입력받아 겹치는 부분은 동일 그룹으로 간주하며 모든 좌표를 입력 받았을 때 몇 개의 그룹이 있는지를 찾는 문제입니다.

 

우선 이 문제를 풀기 위해서는 겹치는 부분 즉 원이 한점이나 두점에서 만나야 동일 그룹이 될 수 있다는 것을 알 수 있습니다. 즉 두점 사이의 거리가 반지름의 합보다 작거나 같으면 동일 그룹이 될 수 있습니다. 따라서 이러한 그룹들을 찾아내어 인접리스트를 만들었습니다. 즉 어떤 진영의 enemy가 어떤 진영들과 통신이 가능한지를 벡터에 집어넣은 뒤 dfs라는 함수를 만들어 동일 그룹을 탐색하여 그룹의 수를 늘리는 방식으로 문제를 해결 하였습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <cmath>
#include <vector>
#include <string.h>


using namespace std;

bool chk[3001]; //검사 했는지를 확인하기 위한 배열 
vector<int> v[3001]; //인접리스트를 저장할 벡터 

void dfs(int n) {
	chk[n] = true; 
	
	for(int i = 0; i < v[n].size(); i++) {
		if(chk[v[n][i]]) 
			continue;
		
		dfs(v[n][i]);  
	}
	
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int T;
	int N,x,y,r;
	int arr[3001][3];
	cin >> T;
	
	int group;
	int groupnum;
	bool flag;
	
	while(T) {
		groupnum = 0;
		cin >> N;
		memset(chk, 0 ,sizeof(chk));
		memset(arr, 0 ,sizeof(chk));
		for(int i = 0; i < N; i++) {
			flag = true;
			cin >> x >> y >> r;
			v[i].clear();
			arr[i][0] = x;
			arr[i][1] = y;
			arr[i][2] = r;
			if(i != 0)
				for(int j = 0; j < i; j++) {
					if((arr[j][0] - arr[i][0]) * (arr[j][0] - arr[i][0])  //두 원이 겹치는 경우 
					   + (arr[j][1] - arr[i][1]) * (arr[j][1] - arr[i][1]) 
					   <= (arr[j][2] + arr[i][2]) * (arr[j][2] + arr[i][2])) {
					   	v[i].push_back(j); // 각각의 벡터에 서로를 저장 
					   	v[j].push_back(i);
					   }
				}
			}
			for(int i = 0; i < N; i++) {
				if(chk[i]) //이미 검사된 그룹의 경우 true 
					continue;
				
				dfs(i); 
				groupnum++; //한 그룹의 검사를 끝낸뒤 그룹의 개수 증가 
			}
					   
		cout<<groupnum<<'\n';
		T--;
	}
	return 0;
}