Union-Find Algorithm

1. Concept

위 그림과 같은 그래프가 당신에게 주어졌다고 보자. 그리고 의문의 사나이가 당신에게 물었다.

"5번 노드와 4번 노드는 연결되어 있나요?"

당신은 너무나도 쉬운 질문이라 쉽게 대답할 것 이다. "아니요?"

우리는 쉽게 수학적으로도 { 1,2,3,5 } , { 4,6 } 인 집합으로 표현할 수 있고, 서로 공통되는 원소가 존재하지 않는, 서로소 집합의 형태인 것을 알 수 있다.

그렇다면 컴퓨터는 어떻게 해당 개념을 이해하고 자료를 찾을 수 있을까?

우리는 오늘 이 방법( Union-Find 합집합 찾기 ) 을 알아볼 것이다.

 

2. Logic

여러개의 노드가 모두 연결되지 않은 초기상태의 그래프에서, 각각 자기 자신만을 원소로 가지고 있을때,각 노드들은 부모 노드를 자기자신으로 설정합니다.

 

Node number	1	2	3	4	5	6
Parent node number	1	2	3	4	5	6

 

이때, 위 그림처럼 2번 노드와 5번 노드가 연결되었을때, 5번 노드의 부모노드는 2로 바뀌게 됩니다. 표도 한번 살펴보겠습니다.

일반적으로 연결되어 부모노드를 합칠때는더 작은 값 쪽으로 합쳐집니다. 방향은 다를수 있습니다.

Node number	1	2	3	4	5	6
Parent node number	1	2	3	4	2	6

이러한 계산 과정을 우리는 합침 ( Union ) 이라고 합니다.

그렇다면 이번엔 더 나아가 5번 노드와 3번 노드가 연결되었을때도 살펴봅시다.

Node number	1	2	3	4	5	6
Parent node number	1	2	5	4	2	6

위와 같이 표현됩니다. 그렇다면 해당 표로 2와 3이 연결되어 있다는 것을 어떻게 파악할 수 있을까요?

먼저 3이 가리키는 부모노드인 5를 찾아가고, 5가 가리키는 2 부모노드를 찾아갈 수 있게 되어 컴퓨터는 "3의 부모노드 또한 1이 되는구나." 라고 파악할 수 있게 됩니다.

이러한 과정을 재귀 함수로 작성한다면 가장 효과적이고 직관적으로 해결할 수 있습니다.

전자 과정, 후자 과정이 두가지가 바로 Union-Find 의 전부 입니다.