백준 10216 Count Circle Groups

노드별로 거리를 계산하고

서로가 통신거리 이내에 있는 노드라면 두 노드를 이어준다( = adj 에 추가한다)

그 후 모든 노드가 탐색될 때 까지 BFS탐색을 여러번 진행하면서 

그래프가 몇개 있는지 계산한다.

#define getDist(x0,y0,x1,y1) ((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1))
#define dbl(r) (r*r)

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <string>
#include <algorithm>

using namespace std;
int testcases;
int N;
int enemy[3001][3];
bool isVisit[3001];
int enemyNum;
int adj[3001][3001];
int adjSize[3001];

int main() {
	cin >> testcases;
	while (testcases--) {
		enemyNum = 0;
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 3; j++) {
				cin >> enemy[i][j];
			}
			isVisit[i] = false;
			adjSize[i] = 0;
			for (int j = 0; j < N; j++) {
				adj[i][j] = -1;
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (i == j) continue;
				int dist = getDist(enemy[i][0], enemy[i][1], enemy[j][0], enemy[j][1]);
				int bound = dbl((enemy[i][2] + enemy[j][2]));
				if (dist <= bound ){
					adj[i][adjSize[i]] = j;
					adj[j][adjSize[j]] = i;
					adjSize[i]++;
					adjSize[j]++;
				}
			}
		}

		for (int i = 0; i < N; i++) {
			if (!isVisit[i]) {
				enemyNum++;
				queue<int> bfs;
				bfs.push(i);
				while (!bfs.empty()) {
					int now = bfs.front();
					bfs.pop();
					for (int iter = 0; iter < adjSize[now]; iter++) {
						int next = adj[now][iter];
						if (!isVisit[next]) {
							bfs.push(next);
							isVisit[next] = true;
						}
					}
				}
			}
		}
		cout << enemyNum << endl;
	}

	return 0;
}