백준/1717/union_find/집합의 표현

백준/1717/union_find/집합의 표현

문제 해석

각각의 부분 집합으로 표현되어 있는 1~n까지의 수들을 합집합 연산을 하면서 해당 집합들이 같은 집합인지를 확인하는 문제입니다.

문제 풀이

우선 각각의 집합은 서로 다른 집합이므로 독립적인 집합이라는 표현에 -1 또는, 각각의 인덱스에 해당하는 수로 vector를 초기화합니다.

vector<int>p(1'000'001, -1);

다음으로 각각의 집합이 합집합 시 어떤 수가 부모가 될지 규칙을 정합니다. 저는 더 작은수가 그 집합을 대표하는 인덱스로 표현되도록 하였습니다.

void union_make(int u, int v)
{
	u = parent_value(u); v = parent_value(v);
	if (u == v)return;
	if (u < v)p[v] = u;
	else p[u] = v;
}

이 때 각각의 집합은 또, 서로 다른 집합으로 이루어 져 있을 수 있으므로 해당 집합의 대표들을 구해야 합니다. 대표들을 구하기 위해서는 현재 집합의 대표를 구하는 수의 대표들로 점점 들어가면 됩니다. 이 때 이렇게 점점 들어가는 방법으로 계속 구할 실 시간 초과가 발생합니다. 이를 방지하기 위해 다음과 같이 모든 수는 대표격 인덱스를 저장할 수 있게 만듭니다.

int parent_value(int num)
{
	if (p[num] == -1)return num;
	return p[num] = parent_value(p[num]);
}

u와 v가 서로 같은 집합인지는 그 대표격의 수를 찾아가서 같으면 같은 집합이고, 다르면 다른 집합으로 표시합니다.

bool union_find(int u, int v)
{
	u = parent_value(u); v = parent_value(v);
	if (u == v)return false;
	return true;
}

풀이

첫번째 풀이

#include<iostream>
#include<vector>
using namespace std;

vector<int>p(1'000'001, -1);

int parent_value(int num)
{
	if (p[num] == -1)return num;
	return parent_value(p[num]);
}

bool union_find(int u, int v)
{
	u = parent_value(u); v = parent_value(v);
	if (u == v)return false;
	return true;
}

void union_make(int u, int v)
{
	u = parent_value(u); v = parent_value(v);
	if (u == v)return;
	if (u < v)p[v] = u;
	else p[u] = v;
}

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

	int n, m = 0;
	// m은 연산의 횟수
	// n은 수의 범위
	cin >> n >> m;

	for (int i = 0;i < m;i++)
	{
		// order_num
		// 0이면 a,b를 같은 집합에 넣어달라는 연산
		// 1이면 a,b가 같은 집합인지 알려달라는 연산
		int order_num, a, b = 0;
		cin >> order_num >> a >> b;
		if (order_num == 1)
		{
			// union_find
			if (!union_find(a, b))
			{
				cout << "YES" << '\n';
			}
			else
			{
				cout << "NO" << '\n';
			}
		}
		else 
		{
			// 합집합
			union_make(a, b);
		}
	}

	return 0;
}

두번째 풀이

#include<iostream>
#include<vector>
using namespace std;

vector<int>p(1'000'001, -1);

int parent_value(int num)
{
	if (p[num] == -1)return num;
	return p[num] = parent_value(p[num]);
}

bool union_find(int u, int v)
{
	u = parent_value(u); v = parent_value(v);
	if (u == v)return false;
	return true;
}

void union_make(int u, int v)
{
	u = parent_value(u); v = parent_value(v);
	if (u == v)return;
	if (u < v)p[v] = u;
	else p[u] = v;
}

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

	int n, m = 0;
	// m은 연산의 횟수
	// n은 수의 범위
	cin >> n >> m;

	for (int i = 0;i < m;i++)
	{
		// order_num
		// 0이면 a,b를 같은 집합에 넣어달라는 연산
		// 1이면 a,b가 같은 집합인지 알려달라는 연산
		int order_num, a, b = 0;
		cin >> order_num >> a >> b;
		if (order_num == 1)
		{
			// union_find
			if (!union_find(a, b))
			{
				cout << "YES" << '\n';
			}
			else
			{
				cout << "NO" << '\n';
			}
		}
		else 
		{
			// 합집합
			union_make(a, b);
		}
	}

	return 0;
}