[Algorithm] Union-Find / DSU(Disjoint-Set Union) 알고리즘 이해하기

Union-Find 알고리즘, 또는 Disjoint-Set Union (DSU) 알고리즘은 효율적으로 서로 겹치지 않는 집합들을 관리하고 병합하는 데이터 구조입니다. 이 알고리즘은 네트워크 연결, 이미지 처리, Kruskal의 최소 신장 트리(MST) 찾기 등에 유용합니다.

Union-Find / DSU(Disjoint-Set Union) Algorithm 개요

Union-Find 알고리즘은 특정 요소들이 서로 연결되어 있는지 확인하고, 연결되지 않은 요소들을 하나의 그룹으로 병합하는 데 사용됩니다. 이 데이터 구조는 주로 그래프 이론에서 동적 연결성 문제를 해결하는 데 사용됩니다.

Union-Find 알고리즘 특징

1. 효율성: Union-Find 알고리즘은 각 연산에 대해 거의 상수 시간 복잡도를 가집니다.
2. 동적 집합 관리: 요소들이 동적으로 추가되거나 병합될 수 있는 상황에서 매우 유용합니다.
3. 트리 구조: 각 집합은 트리 형태로 관리되며, 각 노드는 부모 노드를 가리킵니다.

장점

• 효율적인 병합 및 찾기 연산: 경로 압축과 랭크에 의한 합치기 최적화를 통해 거의 상수 시간 복잡도를 유지합니다.
• 다양한 응용 분야: 네트워크 연결, 이미지 처리, 그래프 알고리즘 등 다양한 분야에서 활용됩니다.
• 단순한 구현: 기본 알고리즘은 비교적 단순하게 구현할 수 있습니다.

단점

• 공간 복잡도: 큰 데이터 세트를 처리할 때 상당한 메모리를 사용할 수 있습니다.
• 초기 설정: 알고리즘이 효율적으로 작동하기 위해서는 초기 트리 구조와 랭크 정보가 필요합니다.
• 특수 케이스 처리: 매우 큰 그래프나 특정 패턴의 입력에 대해서는 성능이 저하될 수 있습니다.

주요 연산

Union-Find 알고리즘은 두 가지 주요 연산으로 구성됩니다:

1. Find: 특정 요소가 속한 집합의 대표(또는 루트)를 찾습니다. 이 연산은 두 요소가 같은 집합에 있는지 확인할 때 사용됩니다.
2. Union: 두 요소가 속한 집합을 하나의 집합으로 병합합니다. 이 연산은 집합을 결합할 때 사용됩니다.

최적화

Union-Find 알고리즘을 최적화하는 두 가지 일반적인 기술이 있습니다:

• 경로 압축(Path Compression): Find가 호출될 때마다 트리 구조를 평탄화하여 노드가 직접 루트를 가리키도록 합니다. 이는 미래의 연산 속도를 높입니다.
• 랭크에 의한 합치기(Union by Rank): 짧은 트리를 더 긴 트리 아래에 붙여 트리를 균형 있게 유지하여 트리의 높이를 작게 유지합니다.

Python 구현

Union-Find 알고리즘은 효율적으로 상호 배타적인 집합들을 관리하고 병합하는 데이터 구조입니다. 이 알고리즘은 그래프에서 연결성을 검사하거나 집합을 병합하는 다양한 문제를 해결하는 데 유용합니다. 다음은 두 가지 최적화가 포함된 Union-Find 알고리즘의 기본 구현입니다:

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))  # 각 노드의 부모를 초기화합니다.
        self.rank = [0] * size  # 각 노드의 랭크를 초기화합니다.

    def find(self, node):
        if self.parent[node] != node:
            # 경로 압축을 통해 노드가 직접 루트를 가리키도록 합니다.
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)

        if root1 != root2:
            # 랭크에 따른 합치기
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            elif self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1

# 사용 예시
uf = UnionFind(10)
uf.union(1, 2)
uf.union(2, 3)
print(uf.find(1))  # 출력: 1
print(uf.find(3))  # 출력: 1

코드 설명

초기화 메서드 (__init__)

def __init__(self, size):
    self.parent = list(range(size))  # 각 노드의 부모를 초기화합니다.
    self.rank = [0] * size  # 각 노드의 랭크를 초기화합니다.

• self.parent: 각 노드의 부모 노드를 나타내는 리스트입니다. 초기에는 각 노드가 자기 자신을 부모로 가집니다.
• self.rank: 각 노드의 랭크를 나타내는 리스트입니다. 초기에는 모든 노드의 랭크가 0입니다.

찾기 메서드 (find)

def find(self, node):
    if self.parent[node] != node:
        self.parent[node] = self.find(self.parent[node])  # 경로 압축
    return self.parent[node]

• 경로 압축을 통해 find 연산의 효율성을 높입니다. 노드가 자신의 루트를 가리키도록 트리를 평탄화합니다.
• 부모 노드가 자기 자신이 아닌 경우, 재귀적으로 부모 노드를 찾고, 현재 노드의 부모를 루트로 업데이트합니다.

합치기 메서드 (union)

def union(self, node1, node2):
    root1 = self.find(node1)
    root2 = self.find(node2)

    if root1 != root2:
        if self.rank[root1] > self.rank[root2]:
            self.parent[root2] = root1
        elif self.rank[root1] < self.rank[root2]:
            self.parent[root1] = root2
        else:
            self.parent[root2] = root1
            self.rank[root1] += 1

• 두 노드의 루트를 찾습니다.
• 두 루트가 다를 경우, 랭크에 따른 합치기를 사용하여 트리를 병합합니다.
  • 랭크가 높은 트리를 낮은 트리 아래에 두어 트리의 높이를 최소화합니다.
  • 랭크가 같은 경우, 하나의 트리를 다른 트리 아래에 두고 랭크를 증가시킵니다.

사용 예시

uf = UnionFind(10)  # 10개의 노드를 가진 Union-Find 구조를 초기화합니다.
uf.union(1, 2)  # 노드 1과 노드 2를 같은 집합으로 합칩니다.
uf.union(2, 3)  # 노드 2와 노드 3을 같은 집합으로 합칩니다.
print(uf.find(1))  # 노드 1의 루트를 출력합니다. (출력: 1)
print(uf.find(3))  # 노드 3의 루트를 출력합니다. (출력: 1)

• uf.union(1, 2): 노드 1과 2를 같은 집합으로 합칩니다.
• uf.union(2, 3): 노드 2와 3을 같은 집합으로 합칩니다.
• uf.find(1), uf.find(3): 노드 1과 3이 동일한 집합에 속하는지 확인합니다.

예제 문제: 비연결 그래프에서 연결된 컴포넌트의 수

다음은 비연결 그래프에서 연결된 컴포넌트의 수를 찾기 위해 Union-Find 알고리즘을 사용하는 예제입니다.

def count_components(n, edges):
    uf = UnionFind(n)
    for edge in edges:
        uf.union(edge[0], edge[1])
    
    root_set = set()
    for i in range(n):
        root_set.add(uf.find(i))
    return len(root_set)

# 사용 예시
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
print(count_components(n, edges))  # 출력: 2

함수 및 코드 설명

Union-Find 객체 초기화

uf = UnionFind(n)

• n개의 노드를 가진 Union-Find 구조를 초기화합니다.
• 각 노드는 초기에는 자기 자신을 부모로 가지는 개별 집합입니다.

모든 간선을 순회하며 Union 연산 수행

for edge in edges:
    uf.union(edge[0], edge[1])

• 주어진 간선 목록을 순회하며, 각 간선에 대해 두 노드를 같은 집합으로 합칩니다.
• 이는 연결된 모든 노드를 같은 컴포넌트로 병합합니다.

루트 집합 생성

root_set = set()
for i in range(n):
    root_set.add(uf.find(i))

• 각 노드의 루트를 찾고, 루트를 root_set에 추가합니다.
• 동일한 컴포넌트에 속하는 노드들은 동일한 루트를 가지므로, root_set에는 고유한 루트만 저장됩니다.

연결된 컴포넌트의 수 반환

return len(root_set)

• root_set의 길이는 고유한 컴포넌트의 수를 나타냅니다.

사용 예시

# 노드의 수와 간선 리스트 정의
n = 5
edges = [[0, 1], [1, 2], [3, 4]]

# 함수 호출 및 결과 출력
print(count_components(n, edges))  # 출력: 2

• n = 5는 5개의 노드를 가진 그래프를 의미합니다.
• edges = [[0, 1], [1, 2], [3, 4]]는 그래프의 간선 리스트입니다.
  • 노드 0, 1, 2는 서로 연결되어 하나의 컴포넌트를 이룹니다.
  • 노드 3, 4는 서로 연결되어 또 다른 컴포넌트를 이룹니다.
• count_components 함수는 2개의 연결된 컴포넌트가 있음을 반환합니다.

Union-Find 알고리즘을 사용하는 경우

Union-Find 알고리즘은 동적 연결성을 다루는 시나리오에서 특히 유용합니다:

• 네트워크 연결: 두 노드가 같은 연결된 컴포넌트에 있는지 확인합니다.
• 이미지 처리: 이진 이미지에서 연결된 컴포넌트를 분할합니다.
• Kruskal 알고리즘: 그래프의 최소 신장 트리(MST)를 찾을 때, 사이클을 효율적으로 감지합니다.

마무리

Union-Find 알고리즘은 그래프 이론에서 동적 연결성을 처리하는 강력한 도구입니다. 이 알고리즘은 효율적인 병합 및 찾기 연산을 제공하여 다양한 응용 분야에서 널리 사용됩니다. 네트워크 연결 상태 확인, 이미지 처리, 최소 신장 트리(MST) 찾기 등 여러 분야에서 Union-Find 알고리즘의 유용성을 확인할 수 있습니다. Python으로 구현된 Union-Find 알고리즘을 통해 기본적인 구조와 최적화 기법을 이해하고, 실제 문제 해결에 적용할 수 있습니다. 이 글을 통해 Union-Find 알고리즘의 개념과 구현, 그리고 응용 사례를 명확히 이해하는 데 도움이 되었기를 바랍니다. 추가적인 심화 학습을 위해 여러 온라인 자료와 논문을 참고하는 것도 좋은 방법입니다.