Union-Find(합집합 찾기)

Union-Find 는 대표적인 그래프 알고리즘이다.
Disjoint-Set이라고 해서 서로소 집합 알고리즘이라고도 부른다.

 

여러 개의 노드가 존재할 때,
두 개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는 지 판별하는 알고리즘

처음에 여러 개의 노드가 서로 자유롭게 존재한다.

이와 같이 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때,

 

첫 번째 행은 '노드 번호'를 의미하고
두 번째 행은 '부모 노드 번호'를 의미한다.

즉, 자신이 어떠한 부모에 포함되어 있는지를 의미한다.

이와 같이 1과 2가 연결되었다고 한다.
이러한 '연결성'을 우리가 프로그래밍 언어로 어떻게 표현할 수 있을 지에 대한 내용이 

바로 Union-Find라고 생각하자.

 

2번째 인덱스의 값에 '1'이 들어가게 된다.
이렇게 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합친다.
이것을 합침(Union)이라고 한다.

 

2와 3도 연결되었다.

 

2와 3이 연결되어서 3번째 인덱스의 값이 '2'로 바뀌었다.

하지만 여기서 1과 3이 연결되었는지 어떻게 파악할 수 있을까?

1과 3은 부모가 각각 1과 2로 다르기 때문에 '부모 노드'만 보고는 한번에 파악할 수 없다.

 

여기서 재귀 함수가 사용된다.

 

3의 부모를 찾기 위해서는 먼저 3이 가리키고 있는 2를 찾는다.
그러면 2의 부모가 1을 가리키고 있으므로 3의 부모는 1이 되는 구나를 알 수 있다.

 

이러한 과정은 재귀적으로 수행될 때 가장 효과적이고 직관적으로 언어를 작성할 수 있다.

그래서 결과적으로 합침(Union)연산이 다 수행되고 나면 

 

노드 1,2,3 의 부모가 모두 1이기 때문에

이 세 가지 노드는 모두 같은 그래프에 속한다고 할 수 있다.

이것이 바로 Union-Find이다.

 

Find 알고리즘은

두 개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘이다.