[G4] 백준 10216번 Count Circle Groups C++ 너비 우선 탐색, 기하학, BFS

리뷰

 

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

좌표를 기준으로 반경이 겹치는 그룹의 개수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• t : 테스트케이스의 개수를 저장할 변수
• n : 노드의 개수를 저장할 변수
• Pos : 좌표와 반지름을 정의할 구조체
• poses : 각 노드의 좌표와 반지름을 저장할 배열
• edges : 각 노드의 인접리스트를 저장할 벡터 배열
• v : 노드 방문 여부를 체크할 배열

 

함수

1. get_dist

double get_dist(const Pos& a, const Pos& b) {
	return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

 

두 좌표 사이의 거리를 구하기 위한 함수

 

2. bfs

void bfs(int sn) {
	queue<int> q;
	q.push(sn);
	v[sn] = true;

	while (!q.empty()) {
		int cn = q.front(); q.pop();

		for (int nn : edges[cn]) {
			if (v[nn]) continue;
			v[nn] = true;
			q.push(nn);
		}
	}
}

 

너비 우선 탐색을 통해 그룹을 짓기 위한 함수

 

 

문제풀이

1. t값을 입력 받고, t번의 테스트케이스를 수행한다.
2. 매 테스트케이스마다 n값을 입력 받고, n개의 좌표와 반지름을 입력 받아 poses배열을 초기화한다.
3. n개의 edges를 clear()처리하여 이전 테스트케이스에서 사용했던 정보를 초기화한다.
4. 모든 노드간 브루트포스로 순회하며 변수 dist에 get_dist함수를 통해 두 좌표의 거리를 저장한다.
5. dist가 각 노드의 반지름의 합보다 작거나 같을 경우 간선을 추가한다.
6. 변수 g를 0으로 초기화하고, memset함수를 통해 v배열을 false로 초기화한다.
7. 1~n번노드를 순회하며 이미 방문한 경우 continue처리한다.
8. 아직 방문하지 않은 노드라면 g를 증가시킨 뒤 bfs함수에 노드 번호를 매개변수로 전달하여 호출한다.
9. bfs함수 내부에서 시작 노드 번호 sn을 매개변수로 전달받는다.
10. 정수형 큐 q를 초기화하고, sn을 추가한 뒤 v배열에 방문처리를 수행한다.
11. q가 빌때까지 while루프를 수행하며, 그래프를 탐색해 그룹을 지어준다.
12. n번 노드까지 탐색을 마친 후 g에 저장된 값을 출력하고 개행문자를 삽입한다.

 

트러블 슈팅

1. 인접리스트를 초기화할때 단방향 간선으로 추가하여 WA를 받았다.
2. 양방향 간선으로 추가하고, bfs내부에서 방문 조건을 추가하여 AC를 받았다.

 

참고 사항

1. 재한값은 N (1 ≤ N ≤ 3,000), x, y (0 ≤ x, y ≤ 5,000), R (0 ≤ R ≤ 5,000)로 정수 범위 내로 풀이가 가능하다.
2. 1-based-indexing을 사용했으므로 최대 n까지 인덱스를 사용할 수 있게 초기화 해주어야 한다.

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;

const int N = 3e3 + 1;
int t, n;
struct Pos {
	int x, y, r;
};
Pos poses[N];
vector<int> edges[N];
bool v[N];

double get_dist(const Pos& a, const Pos& b) {
	return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

void bfs(int sn) {
	queue<int> q;
	q.push(sn);
	v[sn] = true;

	while (!q.empty()) {
		int cn = q.front(); q.pop();

		for (int nn : edges[cn]) {
			if (v[nn]) continue;
			v[nn] = true;
			q.push(nn);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> t;
	while (t--) {
		cin >> n;

		for (int i = 1; i <= n; ++i) {
			int x, y, r; cin >> x >> y >> r;
			poses[i] = { x, y, r };
		}

		for (int i = 1; i <= n; ++i) edges[i].clear();
		for (int i = 1; i < n; ++i) {
			for (int j = i + 1; j <= n; ++j) {
				Pos a = poses[i], b = poses[j];
				double dist = get_dist(a, b);
				if (dist <= poses[i].r + poses[j].r) {
					edges[i].push_back(j);
					edges[j].push_back(i);
				}
			}
		}

		int g = 0;
		memset(v, 0, n + 1);
		for (int i = 1; i <= n; ++i) {
			if (v[i]) continue;
			++g;
			bfs(i);
		}

		cout << g << "\n";
	}
}