[BOJ] 1717 : 집합의 표현

1717 : 집합의 표현

문제

초기에
$n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$ 이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 $n$, $m$이 주어진다.
$m$ 은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다.
합집합은 $0$ $a$ $b$의 형태로 입력이 주어진다.
이는 $a$가 포함되어 있는 집합과, $b$가 포함되어 있는 집합을 합친다는 의미이다.
두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 $1$ $a$ $b$의 형태로 입력이 주어진다.
이는 $a$와 $b$가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

1로 시작하는 입력에 대해서 $a$ 와 $b$가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

풀이

Union-Find 라는 자료 구조를 통해 풀 수 있었다.
주로 그래프 문제에서 연결성 여부를 판단하거나, 서로 다른 집합을 병합하는 데 사용할 수 있다.

• Find: 특정 요소가 속한 집합의 "대표자"를 찾고, 이 과정을 통해 두 요소가 같은 집합에 속해 있는지 확인.
• Union: 두 개의 집합을 하나로 합치기.

int Find(int a)
{
	if(v[a] == a)
    	return a;
    
    return v[a] = Find(v[a]);
}

void Union(int a,int b)
{
	int parent_a = Find(a);
    int parent_b = Find(b);
    
    if(parent_a > parent_b)
    	v[parent_a] = parent_b;
    else
    	v[parent_b] = parent_a;
}

와 같은 방법으로 구현할 수 있다.

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;


int n, m;
vector<int> v;

int Find(int a)
{
	if (v[a] == a)
		return a;
	return v[a] = Find(v[a]);
}

void Union(int a, int b)
{
	int parent_a = Find(a);
	int parent_b = Find(b);

	if (parent_a > parent_b)
		v[parent_a] = parent_b;
	else
		v[parent_b] = parent_a;
}

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

	cin >> n >> m;

	v.resize(n + 1);

	for (int i = 0; i <= n; ++i)
		v[i] = i;

	int a, b, op;

	for (int i = 0; i < m; ++i)
	{
		cin >> op >> a >> b;

		if (op == 0)
			Union(a, b);
		
		else
		{
			if (Find(a) == Find(b))
				cout << "YES" << '\n';
			else
				cout << "NO" << "\n";
		}
	}

	return 0;
}