유니온 파인드 (Union Find, Disjoint set)

유니온 파인드 (Union Find, Disjoint set)

---

  정의 

  유니온 파인드(Union Find) 는 서로소 집합(Disjoint-set) 이라고도 불린다. 이는 집합 혹은 그룹 관리를 효율적으로 할 수 있는 알고리즘 이다. 그룹은 트리의 구조로 관리가 된다. 한 트리에 여러 그룹이 있는 것이 아니라 그룹의 개수만큼 트리가 생성이 되는 것 이다.

---

  설명 

  위 예시의 경우는 두 가지 트리가 존재한다. 그룹이 두 개 존재하는 경우인 것 이다. 두 노드끼리 같은 그룹인지 아닌지 판단하는 기준은 해당 노드의 루트 노드가 같은지 판단하면 된다. 위 예시에서 2, 4번째 노드는 둘 다 루트노드가 1로 동일하다. 따라서 같은 그룹이다. 하지만 3, 6번째 노드는 각각 루트노드가 1, 5번째 노드이다. 따라서 이 두 노드는 같은 그룹에 속해있지 않다.

 

  연결이 되어있는 두 노드의 간선을 추가할 때 그룹화를 시키는 방법은 두 노드중 이미 어느 트리에 속해있는 노드가 있다면 이 노드들은 그 트리(그룹)에 속하게 되고, 두 노드 모두 어느 트리(그룹)에도 속해있지 않다면 이 두 노드가 하나의 트리(그룹)을 만들게 된다.

 

  정리 Note

1. 초기 parent array 를 모두 parent[k] = k 가 되도록 초기화를 한다. 모든 노드들은 초기에 각각 개별적으로 트리(그룹)을 혼자 이루고 있기 때문이다.

2. Union, Find 함수로 두 노드를 그룹화 시키거나, 원하는 노드의 루트 노드를 출력한다.

3. 모든 Union 작업이 끝난 후, parent[k] 가 k'th 노드의 루트노드라는 오해를 하면 안된다. parent[k] 는 말 그대로 k'th 노드의 부모노드 이고 k'th 노드의 루트노드(그룹)을 알고싶으면 Find(k) 를 통해 알 수 있다.

즉,  a 번째 Node와 b 번째 Node 가 같은 Unoin 인지 알고싶다면 Find(a) == Find(b) 여부를 확인하면 된다,

---

  Code 

#include <iostream>
#define MAX 9
#define EDGE 7

using namespace std;

int parent[MAX + 1];

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

void Union(int a, int b) {
	int pa = Find(a);
	int pb = Find(b);
	
	// b 의 parent 를 a 의 parent 로 정의 
	parent[pa] = parent[pb];
}

int main() {
	for (int i = 1; i <= MAX; i++)
		parent[i] = i;

	for (int i = 1; i <= EDGE; i++) { // EDGE 만큼 간선 정의
		int s, e;
		cin >> s >> e;
		Union(s, e);
	}
}