유니온 파인드(with 백준1717)

유니온파인드란?

유니온 파인드는 상호 배타적 집합이라고도 하며

누군가 어떤 집합에 속해있는지 알아내기위해, 또는 집합끼리 합치기 위해 사용하는 

자료구조이다.

구현

트리를 통해서 이 자료구조를 구현하게 되는데 기본은

각 원소마다 배정된 배열에 자신의 index를 넣는것이다 즉 arr[i] = i로 초기화하는 것이다.

이것을 풀어서 설명하면 i의 부모노드는 i 라는것을 의미한다.

먼저 x가 어떤 집합에 포함되어 있는지 찾는 연산인 find함수에 대해 설명하겠다.

다음과 같이 구현이 되어 있다.

일단 if문을 보면 가장 상위 노드까지 올라가면 그 노드를 반환하는 식으로 되어있다.

그렇다면 else문에서 그냥 find함수를 호출하기만 하면 되는데 arr[x] = y라는 과정을 추가했을까

그 이유는 실제로 활용할 때 최악의 경우

트리가 이렇게 한 방향으로만 형성될 수 있기 때문에 노드 수가 많아졌을 경우 

재귀를 통해 가장 상위 노드를 찾는데 문제가 생길 수 있기 때문이다.

그래서 트리를 이런 모양으로 만들어 복잡도를 줄이기 위해 저런 과정을 추가하게 된다.

다음으로는 합치는 함수에 대해 알아보자.

이렇게 간단하게 되어있는데 두개의 노드에 대해 가장 상위노드를 찾은 뒤

한 집합의 상위노드를 다른 집합의 상위노드에 연결하는 식으로 구성되어있다.

유니온 파인드에 대해 대체적으로 이해가 됐다면 다음 문제를 통해 적용해보자.

문제링크 : https://www.acmicpc.net/problem/1717

#include <iostream>

using namespace std;

int arr[1000000];

int find(int x)
{
	if (x == arr[x]) return x;
	else {
		int y = find(arr[x]);
		arr[x] = y;
		return y;
	}
}
void uni(int a, int b)
{
	int x = find(a);
	int y = find(b);
	arr[y] = x;
}
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);

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

	while (m--)
	{
		int num, x, y;
		scanf("%d %d %d", &num, &x, &y);
		if (num == 0)
		{
			uni(x, y);
		}
		else
		{
			if (find(x) == find(y)) printf("YES\n");
			else printf("NO\n");
		}
	}
	for (int i = 0; i <= n; i++) printf("%d ", arr[i]);
}