글 읽기 - disjoint - set 이 틀리는 이유????

shinbian11 3년 전 0

36~45번째 코드를 하니까 틀렸다 나오고, 그 대신 46~50번째 코드로 대체하니까 맞다고 나오는데, 두 코드 덩어리 모두 집합끼리 합친다 라는 정의는 같지 않나요? disjoint - set 처럼 한 건데 왜 36~45번째 코드는 틀린 건가요? 제가 어떤걸 잘못 구현한건지 궁금합니다.

#include <bits/stdc++.h>

// F_I 사용하면 cin 과 scanf 를 섞어서 쓰면 안된다!
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;

ll Min(ll a, ll b) { return (a < b) ? a : b; }
ll Max(ll a, ll b) { return (a < b) ? b : a; }
ll gcd(ll m, ll n) { if (n == 0) return m; return gcd(n, m % n); } //최대공약수
ll lcm(ll m, ll n) { return m * n / gcd(m, n); } //최소공배수

int root[3005];
int Rank[3005];
int tc, n;

int Find(int x)
{
	if (x == root[x]) return x;
	else
	{
		return root[x] = Find(root[x]);
	}
}

void Union(int x, int y)
{
	x = Find(x);
	y = Find(y);
 
    //이 부분!
	/*if (x != y)
	{
		if (Rank[x] < Rank[y])
			root[x] = y;
		else
			root[y] = x;

		if (Rank[x] == Rank[y])
			Rank[x] += 1;
	}*/
	for (int i = 1; i <= n; i++)
	{
		if (root[i] == y)
			root[i] = x;
	}

	return;
}
int main()
{
	F_I;
	
	//int tc;
	cin >> tc;
	while (tc--)
	{
		
		//int n;
		cin >> n;
		vector< tuple<int, int, int> > v(n + 1);

		memset(root, 0, sizeof(root));
		memset(Rank, 0, sizeof(Rank));

		for (int i = 1; i <= n; i++)
		{
			root[i] = i;
			Rank[i] = 0;
		}
		
		for (int i = 1; i <= n; i++)
		{
			cin >> get<0>(v[i]) >> get<1>(v[i]) >> get<2>(v[i]);
		}
		
		double two_radius;
		double dist;
		for (int i = 1; i < n; i++)
		{
			for (int j = i + 1; j <= n; j++)
			{
				two_radius = (double)get<2>(v[i]) + get<2>(v[j]);
				dist = sqrt((get<0>(v[i]) - get<0>(v[j])) * (get<0>(v[i]) - get<0>(v[j])) + (get<1>(v[i]) - get<1>(v[j])) * (get<1>(v[i]) - get<1>(v[j])));
				if (two_radius >= dist)
				{
					Union(i, j);
				}
			}
		}
			
		
		set<int> ans;
		for (int i = 1; i <= n; i++)
		{
			ans.insert(root[i]);
		}
		
		cout << ans.size() << '\n';

	}
	return 0;
}

wider93 3년 전 1

문제는 안 읽어봤지만 100번 줄에서 ans에 넣는 것이 root[i]들이기 때문에 그럴 것 같네요. 항상 최상단의 노드를 찾도릭 Find(i)로 바꾸면 주석처리한 부분도 작동할 겁니다.

shinbian11 3년 전 0

오오 그렇네요. 감사합니다!

그런데 왜 저 부분을 Find(i)로 바꿔서 최상단의 노드를 찾아주어야 하나요?

제가 생각했을떈 이미 Union(i,j) 을 통해서 그 작업을 모두 해준것 같아서요.

그럼 그냥 root[i]의 값을 ans에 넣어도 되지 않나요?

반례가 궁금합니다..

shinbian11 3년 전 0

Union함수에서 이미 부모 노드를 다 찾아서 두 부모노드가 같지 않으면 Rank를 따져서 합쳐주면서 root[i]의 값을 갱신하는 과정을 거쳤는데도 왜 root[i]를 ans에 넣으면 안되는지가 궁금합니다.

wider93 3년 전 1

부모는 변하니까요. a->b, c->d, b->d 순으로 연결하면 a는 d와 연결되어 있지만 root[a]는 아직 d가 되지 못했습니다.

shinbian11 3년 전 0

아아 그렇군요! 이제 이해했습니다 ㅎㅎ 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

disjoint - set 이 틀리는 이유????

shinbian11 3년 전 0

wider93 3년 전 1

shinbian11 3년 전 0

shinbian11 3년 전 0

wider93 3년 전 1

shinbian11 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말