유니온 파인드

1. 유니온 파인드(Union Find)

 - 서로소인 집합들의 정보를 확인(find)하고 조작(union)할 수 있는 자료구조.

 - Union 연산

: 서로소인 집합을 '유니온' 연산을 통해서 같은 집합으로 만들 수 있다. 

- Find 연산

- 두 원소가 같은 집합에 속해있는지 확인할 수 있다. 

 

- 메쏘드

1. init

 - parent[N] 배열을 모두 자기 자신으로 초기화.

 

2. find

- 루트를 반환하는 함수 

- 재귀적으로 짤 수 있음 : 부모가 자신 일 때 종료.

- 경로 압축: 변수에 결과를 반환받은 뒤, parent 를 갱신 후 다시  return

 

3. union

- 두 원소를 받아서 한 집합으로 만드는 함수

- C++의 경우 union이라는 이름은 이미 있어서 다른 함수 이름으로 설정.

- a , b의 부모를 find연산을 통해서 찾는다. 

- 부모가 같다면 이미 같은 집합이므로 종료

- 아니라면 부모를 갱신: 2find를 실행하면서 경로 압축을 했으므로 최고 루트인 부모를 갱신하면 모든 하위 노드들도 갱신되는 효과 .

- 같은 집합에 넣었는지 여부를 bool로 반환할 수 있음. (크루스칼 알고리즘에서 유용)

 

설명 의사코드

Alg init()
	parent를 각각 자기 자신으로 초기화
    
    
Alg union(int a, int b)
	a , b 를 같은 집합에 속하도록 함: 
    a의 부모를 b의 부모로 혹은 b의 부모를 a의 부모로 바꾸도록 한다
	Alg find 사용 {parent[b] = find(a)같은 꼴}
   	이미 부모가 같다면 추가해줄 필요가 없다. {또는 이를 알리기 위해 false를 리턴}
    
    
Alg find(node)
	node의 부모를 찾아준다: 재귀적으로 자기 자신이 부모일 때까지(루트임을 의미)진행.
    - 경로 압축 수행: 재귀를 수행할 때 값을 반환 받아 자신의 부모도 루트로 갱신한다. 
    - 원래는 상위 - 하위 - 하위 - 하위 로 이어지던 집합 구조였다면, 한번 find를 실행하면
    - 상위 - 하위, 구조로 바뀐다. (각자 하위 노드가 가장 상위노드 루트를 가리키게 됨)

 

진짜 pseudo code

/*union find 의 내용 */
void init()
{
	for (int i = 0; i <= N; i++)
		parent[i] = i;
}


int find(int a)
{
	if (parent[a] == a)
		return a;
	int result = find(parent[a]);//root를 반환받는다.
	parent[a] = result;
	return result;
}

bool ft_union(int a, int b)
{
	int roota = find(a);
	int rootb = find(b);
	if (roota == rootb)
		return false; //이미 같은 집합이라서 추가 하지 않았다는 정보 반환
	parent[rootb] = roota;
	return true; //같은 집합에 추가하였다는 사실 반환.
}

bool isUnion(int a, int b)//같은 집합에 속해있는지 참 거짓 반환
{
	return find(a) == find(b);
}

 

2. 크루스칼 알고리즘

- 유니온 파인드 연산을 통해 트리에 간선을 넣는다. Union : 트리(간선의 집합)에 간선 하나를 추가하는 방식. 

더 자세한 크루스칼 알고리즘: to be continued..