[백준 10216] Count Circle Groups (C++)

문제 링크: www.acmicpc.net/problem/10216

10216번: Count Circle Groups

1. 주의할 점

- 유니온 파인드를 사용할 경우, 부모를 저장하는 Par[] 배열이 항상 갱신되도록 해야한다

- 사용하는 메모리들에 대한 초기화를 잘 한다

 

2. 구현

- 입력받음과 동시에 Par[] 배열을 초기화하며 입력받은 데이터들을 V벡터에 넣는다

- 각 통신탑과의 거리를 구하여 반지름의 합보다 작거나 같다면 같은 진영으로 판단 -> Make_union() 함수를 수행한다. N--한다. Make_union() 함수를 수행할 때, 부모 갱신시 조심한다

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct info {
	int x, y, r;
};
info tmp;
int num;
int par[3000];

int find_par(int x) {
	if (par[x] == x) return x;
	return par[x] = find_par(par[x]);
}

void make_union(int a, int b) {
	int pa = find_par(a);
	int pb = find_par(b);
	if (pa != pb) par[pa] = pb;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test, x, y, r;
	cin >> test;
	for (int t = 0; t < test; t++) {
		vector<info> v;
		cin >> num;
		for (int i = 0; i < num; i++) {
			par[i] = i;
			cin >> x >> y >> r;
			tmp.x = x;
			tmp.y = y;
			tmp.r = r;
			v.push_back(tmp);
		}
		int result = num;
		for (int i = 0; i < num - 1; i++)
			for (int j = i + 1; j < num; j++) {
				int fx = v[i].x;
				int fy = v[i].y;
				int fr = v[i].r;
				int sx = v[j].x;
				int sy = v[j].y;
				int sr = v[j].r;
				long long d1 = (fr + sr)*(fr + sr);		//반지름 합
				long long d2 = (fx - sx)*(fx - sx) + (fy - sy)*(fy - sy);		//레이더 사이의 거리
				if (d1 >= d2 && find_par(i) != find_par(j)) {		//같은 그룹
					make_union(i, j);
					result--;
				}
			}
		cout << result << '\n';
	}
	return 0;
}

if (pa != pb) par[pa] = pb; 문장을 유의한다!!