백준 10216번 Count Circle Groups (c++)

 

문제를 보자마자 떠오른것이 유니온파인드였기 때문에 유니온파인드로 해결했다.

 

int n;
vector<pair<int, int>> mp;
vector<int> r;
int parent[5000] = { 0, };

map 자료구조를 사용했다가 시간초과를 왕창받았기에 전부 vector와 배열로 바꿨다.

 

void init()
{
	mp.clear();
	r.clear();
	memset(parent, 0, sizeof(parent));

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		mp.push_back({ a,b });
		r.push_back(c);
		parent[i] = i;
	}
}

테스트케이스의 갯수가 주어지는 귀찮은 문제이기에 init을 함수로 분리했다.

parent 배열도 바로 초기화해준다.

 

int find_parent(int point)
{
	if (parent[point] == point) return point;
	else return find_parent(parent[point]);
}

void make_union(int a, int b)
{
	a = find_parent(a);
	b = find_parent(b);
	if (a == b) return;
	parent[b] = a;
}

유니온파인드 해주는 간단한 함수들

 

bool checkRange(int i, int j)
{
	pair<int, int> a = mp[i];
	pair<int, int> b = mp[j];
	double d = (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
	int rr = (r[i] + r[j]) * (r[i] + r[j]);
	if (d > rr) return false;
	else return true;
}

문제는 결국 원과 원 사이의 관계를 계산하라는것이다.

두 원의 중심과의 거리와 두 원의 반지름의 합을 비교하여

거리가 더 멀면 두 원은 접촉하지 않아 직접 통신이 불가능하고

같거나 가까우면 직접통신이 가능하다는 뜻

 

pow와 sqrt를 쓰면 시간초과가 날 수 있기에 쓰지 않았다.

 

void countGroup()
{
	set<int> s;
	for (int i = 0;i<n;i++)
	{
		s.insert(find_parent(i));
	}
	cout << (int)s.size() << endl;
}

void sol()
{
	for (int i = 0; i < n-1; i++)
	{
		for (int j = i+1; j < n; j++)
		{
			if (i == j)continue;
			if (checkRange(i, j) == true)
			{
				make_union(i, j);
			}
		}
	}
	countGroup();
}

진영은 많아야 3000곳이므로 모든 진영을 1:1 비교해주면서 그룹을 만들면된다.

그리고 생긴 parent배열을 set에 집어넣으며 그룹의 갯수를 세준다.

 

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int t;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		init();
		sol();
	}
}

 

 

 

나의 VS 상에선 문제없이 작동했는데 백준 채점에서는 계속 원인도 안나오는 이상한 컴파일 에러가 나와서 삽질을 많이 했다. 결국 parent 배열을 3500에서 5000으로 늘려줌으로써 해결했는데 이유를 모르겠다.

N은 최대 3000이고 3000이면 충분한거 아닌가라고 생각했는데..