합집합(union find) 알고리즘

합집합 알고리즘(union-find)은 대표적인 그래프 알고리즘으로

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

 

예를 통해 살펴보도록 하죠.

이런 노드들 각각의 부모 노드를 배열로 나타내면 다음과 같습니다.

1 : [1](가장 상위의 노드이므로 같은 숫자가 들어갑니다.)

2 : [1]

3 : [2]

4 : [4]

5 : [5]

여기서 3의 가장 상위에 있는 노드는 1인데 2가 들어가 있습니다.

3에 1을 넣어주기 위해 재귀 함수를 사용합니다.

3의 상위 노드 2의 상위 노드가 무엇인지 계속해서 찾아나갑니다.

그리고 자신의 상위 노드로 갖는 1에 도달하면 그 값을 3의 상위 노드 값으로 변경해줍니다.

3 : [1]

1, 2, 3은 부모가 모두 1이므로 같은 그래프에 속하는 것입니다.

이런 식으로 그래프를 처리하면 두 개의 노드를 선택해 이들이 서로 같은 그래프에 속하는지 판별하는 알고리즘을 쉽게 만들 수 있습니다.

 

정리하면 재귀 함수를 통해 가장 상위의 노드를 파악합니다.

그리고 두 숫자를 뽑아 상위 노드가 같은 지 확인해 같은 그래프에 속하는지 판별할 수 있습니다.