[알고리즘] 상호 배타적 집합 (Disjoint set), 유니온 파인드 (Union find)

상호  배타적 집합이란 서로 다른 특성을 가지고 공통 원소가 서로 존재하지 않는 집합이다.

집합들끼리 팀을 이룬다고 생각하면 된다. 유니온 파인드라고도 한다.

공통 원소가 존재하는지 확인하는 방법은 각 원소가 포함된 트리의 루트 노드가 같은지 비교하는 것이다.

	for (int i = 0; i < n; i++)
    {
	    parent[i] = i;
      	    rank[i] = 1;
    }

먼저 배열을 하나 만들고 자기 자신을 부모로 설정한다.

루트 노드가 자신이고 높이가 1인 트리 n+1개가 만들어진다.

	int Find(int u)
	{
		if (u == parent[u])
			return u;

		return Find(parent[u]);
	}

Find함수는 재귀적으로 루트노드를 반환하는 함수이다.

그런데 함수의 문제점이 있는데 한쪽 방향으로 트리가 치우치면 한단계씩 다 탐색하기 때문에 굉장히 비효율적이다.

 

	int Find(int u)
	{
		if (u == parent[u])
			return u;

		return parent[u] = Find(parent[u]);
	}

parent[u] = find(parent[u])로 부모를 저장해주면 루트노드를 찾는 과정히 상당히 압축된다.

 

출처: https://soobarkbar.tistory.com/

a에서 find(0)을 하면 b처럼 경로가 압축된다.0의 부모를 거쳐간 노드들은 모두 부모로 루트노드를 가리키도록 최적화했다.

 

void Union(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;

	if (rank[u] > rank[v])
		swap(u, v);

	parent[u] = v;

	if (rank[u] == rank[v])
		rank[v]++;
}

Union은  u가 속해있는 집합과 v가 속해있는 집합을 합치는 함수이다. 

먼저 u와 v r 각각의 루트 노드를 구한다. 같다면 같은 트리에 속해있는 것이므로 합칠 필요가 없다.

그리고 트리의 높이가 더 낮은 쪽을 높은 트리의 서브 트리로 포함시킨다.

두 트리의 높이가 같을 경우 높이를 1 증가시킨다.