[알고리즘] 유니온-파인드(Union-Find) & 서로소 집합(Disjoint Set) 개요 및 개념

상호 배타적, 즉 공통 원소가 없는 집합 간의 관계를 서로소 집합이라고 합니다. 그리고 이렇게 교집합이 공집합인 집합(서로소 집합)들을 효율적으로 관리(확인[Find]과 조작[Union])하기 위한 자료구조를 유니온-파인드라고 합니다.

서로 다른 집합을 병합(Union)하고 원소가 어느 집합에 속해있는지 확인(Find)하기 위한 연산을 제공하기 때문에 이러한 이름이 붙게 되었습니다. 원소의 같은 집합 찾기 문제나 같은 동맹군 찾기 문제에 활용할 수 있는 자료구조입니다.

유니온-파인드(Union-Find)란?

Union 연산은 다음과 같은 기능을 합니다.

• 어떤 두 원소 \( a,b \) 에 대해서 각 원소가 속한 집합을 하나로 합치는 연산
• \( a \in A, b \in B \) 에 대해서, \( union(a,b) \) 는 \( A \cup B \) .

Find 연산은 다음과 같은 기능을 합니다.

• 어떤 원소 \( a \) 에 대해서 \( a \) 가 속한 집합을 반환
• \( a \in A \) 에 대해서, \( find(a) \) 는 A를 반환

유니온-파인드(서로소 집합) 표현

유니온-파인드의 연산을 그림으로 표현하며 연산을 살펴보겠습니다.

유니온-파인드의 연산은 배열(Array) 혹은 트리(Tree) 자료구조를 이용해 구현할 수 있습니다.

초기화(init), Union, Find 연산을 배열과 트리의 도식으로 함께 보겠습니다.

초기화(init) 연산

먼저 모든 원소를 각 원소가 속한 부모 원소를 가리키도록 구현해야 합니다. 이때, 배열은 배열 내용에 인덱스를 저장함으로써 부모 원소의 인덱스를 가리키게 됩니다. 초기화에서는 자기 자신을 가리키게 됩니다.

유니온-파인드 초기화

위 그림과 같이 배열은 자신의 인덱스를 가리켜 초기화되고, 트리 역시 자신을 카리켜 초기화가 됩니다.

Union 연산

Union 연산은 Find 연산을 통해 한 원소의 부모 원소를 찾고 다른 원소 역시 Find 연산을 통해 부모 원소를 찾고 그 원소에 먼저 찾았던 부모 원소를 저장하여 같은 집합으로 병합하게 됩니다. (Union 연산(2)에서 더 자세히 설명하겠습니다.)

유니온-파인드 Union

위 그림과 같이 union(1, 2)는 2가 1을 가르킴으로써 병합하게 되고 union(3, 5)는 5가 3을 가르킴으로써 병합하게 됩니다. 

Find 연산

Find 연산은 원소가 가르키는 부모 원소의 값을 재귀적으로 반환하여 해당 원소의 부모 원소를 반환하게 됩니다.

유니온-파인드 Find

위 find(2)는 1을 반환하는 것처럼 보이지만 사실 반환된 1의 부모 원소인 1을 반환한 값입니다. 즉, 자신을 가리키는 1, 3, 5의 원소처럼 최종 부모 원소, 즉 루트 원소의 값만이 \( O(1) \) 로 반환되고 다른 원소를 부모로 가지는 원소들은 루트 원소를 재귀적으로 반환 받게 됩니다. 하지만 모든 원소를 \( O(1) \)의 수행시간과 가깝게 반환되도록 구성하는 방법이 존재합니다. (코드 구현에서 더 자세히 설명하겠습니다.)

 

Union 연산(2)

이제 서로 다른 원소를 가리키고 있는 원소들을 Union 연산을 해보겠습니다.

유니온-파인드 Union(2)

위 그림에서 union(2, 5) 연산을 진행했는데 3의 값이 변한 것을 알 수 있습니다. 그 이유는 find(2)를 통해 1을 반환하고 find(5)를 통해 5의 부모원소인 3이 반환된 1을 받아 저장한 것입니다. 다시 union(5, 4) 연산에서는 find(5) 연산을 통해 5 -> 3 -> 1이 반환되고 결국 4의 부모원소는 1이 저장되게 되는 것입니다.

유니온-파인드 구현 (C++)

이제부터 유니온-파인드 자료구조를 C++ 언어로 구현합니다. find 함수의 재귀적 연산 방식과 더 효율적인 탐색 함수를 비교하여 구현하겠습니다.

초기화

배열로 구현된 유니온-파인드의 초기화 코드입니다. 자신의 index를 가리키도록 간단하게 작성할 수 있습니다.

for(int i=1; i<=n; i++){
        parent[i] = i; // 자신의 index를 가리킴
}

Union

union 함수 역시 간단히 구현됩니다. a와 b의 루트 원소를 반환하는 find 함수를 호출하고 한 원소의 루트 원소 값에 다른 원소의 루트 원소 index를 저장만 하면 병합 과정이 완료되는 것입니다.

void cunion(int a, int b){
    int pa = find(a); // a의 루트 원소 index
    int pb = find(b); // b의 루트 원소 index
    parent[pb] = pa; // b의 루트 원소의 부모 원소는 a의 부모 원소 -> 병합
}

Find

find 함수를 먼저 재귀 형태로 작성하면 다음과 같이 작성할 수 있습니다. 자신을 가리키는 원소만 그 값을 반환합니다. 그 외 원소들은 부모 원소의 부모 원소의 부모 원소... 이런 식으로 최종 루트 원소를 찾아 반환하게 됩니다.

int find(int a){
    if(parent[a] == a) return a; // 자신을 가리키는 index의 경우 자신 반환 (루트 원소)
    return find(parent[a]); // 루트 원소를 찾을 때까지 재귀 호출
}

 

하지만 이런식으로 구현될 경우 최악의 경우에 \( O(n) \) 의 수행시간을 가지게 됩니다. 그 이유는 아래 도식으로 설명됩니다.

유니온-파인드 최악의 Find

위 그림과 같이 find(5) 함수는 1을 반환하기 위해 4->3->2->1 이라는 긴 여정을 거쳐 반환하게 됩니다. 이 경우 연산속도의 저하뿐만 아니라 무수히 많은 데이터가 존재한다면 반복된 수많은 함수 호출 때문에 스택 메모리의 오버플로우(Overflow)가 발생할 수도 있습니다. 아래 코드는 이러한 문제를 방지하고 \( O(\textbf{log}n) \) 의 수행시간으로 효율성을 향상시켜 작성한 코드입니다.

int find(int a){
    if(parent[a] == a) return a; // 자신을 가리키는 index의 경우 자신 반환 (루트 원소)
    return parent[a] = find(parent[a]); // 재귀 호출 후에 루트 원소에 저장하여 반환
    // return find(parent[a]); // 루트 원소를 찾을 때까지 재귀 호출
}

 

처음으로 반환할 때는 재귀로 호출하여 루트 원소를 탐색하지만 결국에는 바로 루트 원소 값을 저장하여 반환하기 때문에 이후에는 다시 탐색할 경우에는 더 빠른 속도로 탐색이 가능해집니다. 아래 도식을 통해 바뀐 탐색 방법을 확인할 수 있습니다. 

유니온-파인드 압축된 Find

이제 기존 4를 가리켰던 5는 4가 가르키는 1로 갱신되어 반환되게 됩니다. 다음에 호출될 때는 더 빠른 속도로 바로 1이 반환되게 됩니다.

시간복잡도

이제 본 유니온-파인드 자료구조의 시간복잡도를 확인하겠습니다.

먼저 Find의 경우에는 노드의 갯수가 N이라면 Union 과정을 통해 만들어진 트리의 최대 높이는 \( \textbf{log}N \) 이 됩니다. 따라서 최악의 Find 수행시간은 \( O(\textbf{log}N) \) 이 됩니다.

Union의 수행시간은 Find의 수행시간에 영향을 받게 됩니다. 따라서 N개의 노드를 가진 트리가 M개의 Union 연산을 수행하게 된다면 \(  O(M\textbf{log}N) \) 이 됩니다. 이는 극도로 빠르게 증가하는 아커만 함수의 역함수 \( \alpha (N) \)로 치환되어 결국 \(  O(\alpha(N)) \) 의 수행시간을 가지게 되는데 이는 결국 상수시간 \( O(1) \) 에 수렴되게 됩니다. (압축된 Find 연산일 경우)

결론

서로소(서로 다른 집합)인 원소들을 병합하거나 같은 집합의 원소인지 확인하기 위해 유니온-파인드 자료구조를 사용하면 매우 효율적으로 구현할 수 있음을 알게되었습니다. 특히 원소의 개수에 구애받지 않는 상수 시간만에 연산을 수행하는 놀라운 연산 속도를 보여주는 자료구조입니다.

다음 포스팅에서는 유니온-파인드를 사용한 예제 문제들을 살펴보고 풀이하겠습니다.

또한, 유니온-파인드 자료구조가 활용되는 최소신장트리(MST) 알고리즘 중 하나인 크루스칼(Kruskal) 알고리즘에 대한 포스팅은 다음 링크에서 확인할 수 있습니다.