개요

유니온 파인드는 Disjoint Set (서로소 집합) 또는 Merge-Find Set (병합-찾기 집합) 으로 불리며, 서로소인 집합들을 표현하는 자료구조입니다. 여기서 서로소 집합이란, 각 집합 간에 교집합의 원소가 하나도 없으며, 모든 집합의 합집합이 전체 원소를 포함하는 경우를 의미합니다. 유니온 파인드는 기본적으로 union(집합 병합)과 find(루트 찾기)라는 두 가지 연산만을 지원합니다.

예시

초기 상태에서는 다음과 같은 8개의 서로소 집합이 존재한다고 가정하겠습니다.

{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}

위 상태는 초기의 크기가 8인 유니온 파인드 자료구조를 나타내며, 각각 독립적인 집합을 포함하고 있습니다.

몇 번의 연산이 이루어진 후, 다음과 같은 형태로 집합이 병합되었다고 가정해보겠습니다.

{1, 2, 5, 6, 8}, {3, 4}, {7}

아래 그림은 병합 이후의 상태를 트리 구조로 표현한 것입니다.

트리에서 가장 위에 있는 노드를 루트(root) 라고 하며, 해당 트리에 속한 모든 정점은 동일한 집합에 속해 있습니다. 같은 집합을 표현하는 방법은 여러 가지가 있을 수 있으며, 위 그림은 그 중 하나의 예시입니다.

구현

find 연산

find 연산은 두 원소가 같은 집합에 속해 있는지 확인하기 위해 사용됩니다. 이를 위해 두 원소의 루트를 찾아서 루트가 동일한지 비교합니다. find 연산은 특정 원소의 루트를 찾아주는 역할을 합니다.

다음은 find 연산의 기본 구현입니다.

/**
 * 원소 n을 받아 n의 root 노드를 반환합니다.
 * @param n 루트를 찾을 정점
 * @return root 노드
 */
int find(int n) {
    if (parent[n] < 0) {
        return n; // 자신이 루트 노드일 경우
    }
    return find(parent[n]); // 재귀적으로 부모 노드를 따라 올라감
}

위 코드는 parent 배열을 사용하여 각 노드의 부모를 저장한다고 가정한 구현입니다. 여기서 루트 노드는 parent[n] < 0으로 표시됩니다. 하지만 이 방식에는 단점이 있습니다. 예를 들어, 위 그림과 같은 트리에서 find(6)을 호출하면, 경로가 일직선으로 길어질 경우 많은 재귀 호출이 발생하게 됩니다.

이를 개선하기 위해 경로 압축(path compression) 을 적용할 수 있습니다. 아래는 경로 압축을 적용한 개선된 코드입니다.

int find(int n) {
    if (parent[n] < 0) {
        return n;
    }
    parent[n] = find(parent[n]); // 부모를 루트로 직접 설정하여 경로 압축
    return parent[n];
}

경로 압축은 재귀 호출 과정에서 트리의 구조를 평평하게 만들어줍니다. 따라서 이후의 find 연산이 더 빠르게 수행될 수 있습니다. 경로 압축을 적용한 결과는 아래 그림과 같이 나타납니다.

경로 압축을 적용한 find 연산의 시간 복잡도는 매우 효율적이며, 이론적으로 \( O(\log^* N) \)이라고 표현됩니다. 여기서 \( \log^* N \)은 로그 스타 함수라고 불리며, 매우 느리게 증가하기 때문에 실질적으로 상수 시간에 가까운 성능을 보입니다.

로그 스타 함수

로그 스타 함수(\( \log^* N \))는 반복 로그 함수라고도 불리며, 매우 느리게 증가하는 함수입니다. 이는 다음과 같이 정의됩니다:

  • \( \log^* N \): 어떤 양수 \( N \)에 대해 로그를 반복적으로 취해 그 결과가 \( 1 \) 이하가 될 때까지 몇 번 로그를 취했는지를 나타냅니다.

예를 들어:

  • \( N = 16 \): \( \log_2(16) = 4 \), \( \log_2(4) = 2 \), \( \log_2(2) = 1 \). 따라서 \( \log^*(16) = 3 \).
  • \( N = 2^{65536} \): 매우 큰 값임에도 불구하고 \( \log^*(N) = 5 \).

union 연산

union 연산은 두 개의 서로소 집합을 하나로 합치는 작업을 수행합니다. 유니온 파인드 자료구조에서는 find 연산과 union 연산만 제공되며, 한 번 합쳐진 집합을 다시 분리하는 것은 어렵습니다. 그러나 보통 합치는 작업만 필요한 경우에 유용하게 사용됩니다.

다음은 union 연산의 기본 구현입니다.

void merge(int a, int b) {
    a = find(a); // a의 루트를 찾음
    b = find(b); // b의 루트를 찾음
    
    if (a != b) {
        parent[b] = a; // b의 루트를 a로 변경하여 병합
    }
}

위 코드에서는 두 원소 \( a \)와 \( b \)가 속한 집합의 루트를 각각 찾은 후, \( a \)와 \( b \)가 서로 다른 집합에 속해 있을 경우 \( b \)의 루트를 \( a \)로 설정하여 병합합니다.

여기서 함수명을 merge로 사용한 이유는 C 언어에서 union이 예약어로 사용되기 때문입니다. 실제 구현에서는 union이라는 이름 대신 다른 이름을 사용하는 경우도 많습니다.

시간 복잡도

  • find 연산: 경로 압축을 적용하면 이론적으로 \( O(\log^* N) \), 실질적으로 상수 시간에 가까움.
  • union 연산: find 연산에 의존하므로 동일하게 \( O(\log^* N) \).

따라서 크기가 \( N \)인 유니온 파인드 자료구조에서 \( M \)번의 union 또는 find 연산을 수행할 경우 최악의 시간 복잡도는 \( O(M \cdot \log^* N) \)입니다.

참고자료: