Union Find 알고리즘 [C언어]

유니온 파인드란?

• 대표적인 그래프 알고리즘
• 두 노드가 같은 집합에 속하는지 판별하는 알고리즘
• 합집합 찾기 알고리즘이라고도 불림
• 서로 연결되어 있지 않은 노드를 판별할 수도 있어서 서로소 집합(Disjoint-set) 이라고도 부름
• 노드를 합치는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어짐

1. union(a, b) -> a와 b가 하나인가?
2. find(a) -> a 의 부모 찾기
3. set 함수 -> 함수를 초기화

이해하기

i	1	2	3	4	5	6
p[i]	1	2	3	4	5	6

위와 같이 노드들이 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을때 모든 값이 자기 자신을 가리키도록 만든다. 위의 표는 부모 테이블로 i 는 노드 번호, p[i] 는 부모 노드 번호를 의미한다. 현재 p[i] = i 를 나타낸다.

i	1	2	3	4	5	6
p[i]	1	1	3	4	5	6

Union(1, 2) 를 해주어 노드를 연결하면 표가 아래와 같이 변경된다. 1과 2중에서 더 작은 값이 부모가 되게 한다.

i	1	2	3	4	5	6
p[i]	1	1	1	4	5	6

1, 2 가 연결된 상태에서 3이 추가로 연결되면 위와 같이 표현된다.
위 표에서 1과 3은 부모가 달라서 둘이 연결되어있는지 파악이 어렵다. 이를 위해 재귀함수를 사용하여, 3의 부모인 2를 찾고 2의 부모인 1을 찾아 결과적으로 3의 부모가 1이 되는 것을 파악할 수 있다.

-> 따라서 Union 연산이 모두 수행되고 나면 아래와 같은 표가 완성된다.

i	1	2	3	4	5	6
p[i]	1	1	1	4	5	6