[Data Structure] Union-Find

유니온 파인드

• 그래프 알고리즘의 일종으로, 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.
• 이는 다른 말로 서로소 집합 혹은 Disjoint-Set이라 부른다.

• 즉, 유니온 파인드 연산은 그래프에서 특정 두 노드가 서로 연결되어 있는지 아니면 연결되지 않았는지 판별하기 위한 알고리즘이다.

• 유니온 알고리즘은 기본적으로 배열을 이용한다. 각각의 노드들은 배열에 자기 자신의 값을 가지고 있다. 이상태에서 노드는 단절된 상태이다.

• 만일, 123과 67을 연결하는 간선을 추가하고 싶다면,

• 2번 배열은 1번에 연결되므로 값을 1로 변경, 3번 배열은 값 2번 배열에 연결되므로 값을 2로 변경한다. 6과 7도 마찬가지로 이를 시행한다.

• 위 처럼 여러 노드를 연결하여 그래프를 구성하는 방법도 위와 동일하다.

---

• 이제, 기본적으로 유니온 파인드가 어떤식으로 자료를 저장하는지 알아보았다.
  그렇다면, 유니온 파인드의 이름에서도 알 수 있듯 'Union'연산과 'Find'연산을 구현해야한다. 또한 배열에 존재하는 값들을 연결해 줄 'merge' 연산도 요구된다. 각 연산이 행하는 일은 다음과 같다.
  
  • Union: 두 노드가 연결되어 있는지 판별하는 함수
  • Find: 사용자가 요구하는 변수를 찾는 함수
  • Merge: 노드를 연결해주는 함수
• C++로 구현하면 다음과 같다.

#include <iostream>
#define NODE 9

int arr[NODE];

// 주어진 매개변수 x를 찾는 함수
// 경로압축
// 모든 경로가 부모를 가리키게 만든다.
int find(int x)
{
	if(arr[x] == x)
		return x;
	return arr[x] = find(arr[x]);
}

// find 연산을 통해 각 노드의 루트 노드를 탐색한다.
// 만일 두 노드의 루트 노드가 같다면, 이미 연결된 것이다.
// 그렇지 않다면, 배열의 y인덱스에 x값을 저장한다.
void merge(int x, int y)
{
	x = find(x);
	y = find(y);
	
	if(x == y) return;
	
	arr[y] = x;
}

bool isUnion(int x, int y)
{
	x = find(x);
	y = find(y);
	
	if(x == y) return true;
	return false;
}