[백준] 10216번 Count Circle Groups

문제: 10216번: Count Circle Groups

 

#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

struct circle {
	int x; // x 좌표
	int y; // y 좌표
	int r; // 통신 영역 거리
};
vector<circle> circles;
vector<int> circlesSet;

// 해당 원이 속한 집합 번호를 반환하는 함수
int find_set(int u) {
	if (circlesSet[u] == u)
		return u;
	return circlesSet[u] = find_set(circlesSet[u]);
}

// 두 개의 원 합치기
void union_(int u, int v) {
	int ur = find_set(u);
	int vr = find_set(v);

	// 서로 다를 때 합치면 됨
	// 같다는 건 이미 같은 집합에 속하는 거니까 또 합칠 필요 없음
	if (ur != vr)
		circlesSet[vr] = ur;
}

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

	int t;
	cin >> t;
	while (t-- > 0) {
		int n; // 진영의 숫자
		cin >> n;
		circles = vector<circle>(); // circle 을 저장할 벡터
		
		circlesSet = vector<int>(n); // 각 원이 어느 집합에 속해있는지 지정할 벡터
		for (int i = 0; i < n; i++)
			circlesSet[i] = i;

		for (int i = 0; i < n; i++) {
			int x_, y_, r_;
			cin >> x_ >> y_ >> r_;

			// 정보 세팅
			circle cir;
			cir.x = x_;
			cir.y = y_;
			cir.r = r_;

			circles.push_back(cir);
		}

		// n 의 범위가 0부터 3000까지니까 2중 반복문 돌 수 있음
		for (int i = 0; i < circles.size(); i++) {
			for (int j = 0; j < circles.size(); j++) {
				if (i == j) continue; // 같은 원끼리는 그냥 넘어가기..

				int x1, y1, r1;
				int x2, y2, r2;
				x1 = circles[i].x, y1 = circles[i].y, r1 = circles[i].r;
				x2 = circles[j].x, y2 = circles[j].y, r2 = circles[j].r;

				// 두 원의 원점 사이의 거리보다 각 원의 반지름의 합이 크거나 같으면 영역이 겹치거나 닿음
				// 즉, 이 경우에 union 해주기
				if (((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= (r1 + r2) * (r1 + r2))) {
					union_(i, j);
				}
			}
		}

		int cnt = 0;
		for (int i = 0; i < circlesSet.size(); i++) {
			// 각 집합의 부모 노드는 자기 자신의 번호를 가지고 있으니까.. 이에 해당하는 애들만 세주면 됨.
			if (circlesSet[i] == i) cnt++;
		}
		cout << cnt << "\n";
	}

	return 0;
}

 

개인적으로 너무 어려웠다!!!!!!!! 이게 어떻게 골드 5인지 모르겠다. 내가 기하학에 매우 약해서 그런 것 같기도 하고 그리고 지금까지는 한 점이 입력으로 주어지는 경우만 풀어봤는데 이제는 입력으로 좌표가 들어오니까 이를 어떻게 union 파인드를 이용할 수 있을까라는 고민이 들었다. 

 

일단 두 좌표의 통신 영역이 겹치거나 만나는지의 여부를 알 수 있는 방법은 두 좌표의 원점 사이의 거리와, 두 좌표가 가지는 r 값을 비교하는 것이다. 만약 두 원점 사이의 거리가 각 r 의 값을 합친 값보다 작거나 같다면 이는 두 좌표의 통신 영역이 서로 겹치거나 만난다는 것을 의미한다. 

 

막상 보면 쉽게 이해가 가는데 처음에 떠올리는게 쉽지 않았다. 나는 진짜 수학을 너무 못한다.. 그래도 열심히 해봐야겠지....

 

아무튼 다음으로 어려웠던건 좌표를 어떻게 union find 에 대칭시키는가였는데 이것도 생각보다 간단했다. 그저 index 를 각 circle 의 고유 번호로 할당한 다음에 이를 이용해서 합쳐주면 되는 것이었다;; 이것도 이번 기회에 알게 되었으니 앞으로 계속 써먹으면 좋겠다는 생각이 들었다.

 

마지막으로 출력값은 어떻게 구할 수 있는지에 대해서 말해보자면, 일단 문제에서 출력으로 원하는 값은 총 그룹의 개수였다. 서로 같은 집합에 있는 좌표들은 하나의 그룹으로 취급한다는 사실을 알고 답을 구하면 다음과 같다.

일단 각 circlesSet 값은 해당 circle 이 속해있는 집합의 번호가 적혀있다. 각 그룹의 좌표들의 부모 좌표는 집합의 번호와 index 번호가 같음을 이용하면 쉽게 해결할 수 있다. 즉, 인덱스 번호와 circlesSet 요소의 값이 같은 애가 있다면 cnt++ 해주는 식으로 구할 수 있다.

 

 

 

참고자료:

[백준 10216번] [Kotlin] Count Circle Groups

[백준 10216번] [Kotlin] Count Circle Groups

[C++] 10216번 / Count Circ.. : 네이버블로그

[C++] 10216번 / Count Circle Groups