Algorithm // Union Find

Alpha, Orderly·2025년 1월 29일

aLGORITHM

목록 보기

2/3

용도

Union-Find 자료구조는 **서로소 집합(Disjoint Set)**을 표현하고 관리하는 데 유용한 알고리즘이다. 보통 동일한 그룹에 속하는 요소들 간의 연결 여부를 효율적으로 확인할 때 사용된다.

대표적인 활용 사례는 다음과 같다:

그래프에서 사이클 검출: 크루스칼 알고리즘에서 최소 신장 트리를 만들 때, 간선들을 추가하면서 사이클이 발생하는지를 빠르게 확인할 수 있다.
네트워크 연결 여부 확인: 네트워크의 노드들이 같은 집합에 속하는지 검사하여 연결성을 판별한다.
이미지 처리: 픽셀 간의 연결성을 그룹화하여 영역을 분할하는 데 사용할 수 있다.
사회적 네트워크 분석: 사용자가 같은 그룹에 속하는지를 확인하여 커뮤니티를 나누는 데 활용된다.

Union-Find는 Find 연산과 Union 연산을 지원하며, 경로 압축(Path Compression) 및 랭크 기반 합치기(Rank-based Union)를 적용하면 **거의 상수 시간(O(α(N)))**에 실행할 수 있다. 여기서 α는 역아커만 함수(Inverse Ackermann Function)이며, 실제 데이터 크기에서는 거의 상수에 가깝다.

구현 및 설명

아래 코드는 Union-Find 자료구조를 구현한 것이다. 경로 압축과 랭크 기반 합치기를 적용하여 최적화된 방식으로 Union-Find를 구현하였다.

class UnionFind:
    def __init__(self, n):
        # parent[x] => x의 부모노드를 의미한다.
        self.parent = [i for i in range(n)]
        # rank[x] => x의 트리의 높이를 의미한다.
        self.rank = [1 for _ in range(n)]

    def find(self, x):
        # self.parent[x] 가 x 자기 자신이 아니라면, 루트가 아니고, 계속 루트를 찾아간다.
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
            
        # 찾은 루트를 반환한다.
        return self.parent[x]
    
    def union(self, x, y):
        # x와 y의 루트를 찾는다.
        x_root = self.find(x)
        y_root = self.find(y)
        
        # 루트가 다르면 합친다.
        if x_root != y_root:
            # y의 루트의 높이가 더 크면 x 루트의 부모가 y 루트가 된다.
            if self.rank[x_root] < self.rank[y_root]:
                self.parent[x_root] = y_root
            # x의 루트의 높이가 더 크면 y 루트의 부모가 x 루트가 된다.
            elif self.rank[x_root] > self.rank[y_root]:
                self.parent[y_root] = x_root
            # 높이가 같으면 y 루트의 부모가 x 루트가 되고, x 루트의 높이를 1 증가시킨다.
            else:
                self.parent[y_root] = x_root
                self.rank[x_root] += 1

그래프에서 사이클 검출 예제

아래 예제는 그래프에서 사이클이 발생하는지 검사하는 코드이다.

from typing import List

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        union = UnionFind(len(edges) + 1)

        for f, t in edges:
            # 사이클이 발생하는지 확인
            if union.find(f) == union.find(t):
                return [f, t]
            # 사이클이 없으면 union 수행
            else:
                union.union(f, t)

        return -1