[자료구조] 유니온-파인드 (Union & Find)

유니온-파인드(Union-Find) 자료구조는 서로소 집합(Disjoint Set) 을 효율적으로 관리하는 자료구조입니다. 여러 개의 원소가 있을 때, 원소가 어떤 집합에 속해 있는지를 빠르게 찾고, 두 집합을 하나로 합치는 연산을 수행할 수 있습니다.

 

 

 

유니온-파인드가 필요한 이유

유니온-파인드는 그래프 알고리즘에서 연결된 요소(Connected Components) 를 찾을 때 많이 사용됩니다. 즉, 네트워크에서 두 컴퓨터가 같은 네트워크에 속해 있는지를 판단할 때 사용할 수 있습니다. 또한 Kruskal 알고리즘(최소 신장 트리, MST) 을 구현할 때 필수적으로 사용됩니다.

 

 

유니온-파인드 동작 과정

경로 압축, 랭크 기반 합치기 기법 등 실제로 구현해보는게 이해가 빠르기 때문에 아래와 같이 동작할 수 있는 알고리즘을 구현해봅시다. 대략적인 동작 과정을 먼저 이행하고, 실제 구현에 들어가면 좋습니다.

 

1. 처음에는 각 원소 자신이 부모(루트) 노드가 됩니다.

초기 상태: {1}, {2}, {3}, {4}, {5}

 

2. 여기서 union(1, 2)를 수행하면 {1, 2} 집합이 생성됩니다.

{1,2}, {3}, {4}, {5}

 

3. union(2, 3)을 수행하면 {1, 2, 3} 집합이 생성됩니다.

{1,2,3}, {4}, {5}

 

4. find(3)을 수행하면 3이 속해 있는 집합의 부모(루트) 노드를 반환합니다.

경로 압축 기법을 적용하여 find(3)을 수행하면 3의 부모를 1로 설정하여 빠르게 접근할 수 있도록 합니다.

 

 

유니온-파인드 동작 구현 코드

Find 연산과 Union 연산은 일반적으로 거의 O(1)의 시간 복잡도를 가집니다. (참고)
구현을 해도 어려울 수 있습니다. 그럴때는 혹시 디버거를 쓸 수 있으면 개발환경에서 디버거로 값의 변화를 관찰하는 것도 하나의 방법이 될 것 같습니다. 

# 유니온-파인드 함수 구현
class UnionFind:
   def __init__(self, n):
      self.parent = [i for i in range(n)]  # 처음엔 각 노드가 자기 자신을 부모로 가짐
      self.rank = [1] * n

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

   def union(self, x, y):
      root_x = self.find(x)
      root_y = self.find(y)
      
      # 한 쪽을 다른 쪽에 연결
      if root_x != root_y:
         if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
         elif self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
         else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

# 사용 예제
uf = UnionFind(5)  # 5개의 원소 생성 (0~4)
uf.union(0, 1)  # 0과 1을 합침
uf.union(1, 2)  # 1과 2를 합침 (즉, 0-1-2 연결됨)
print(uf.find(2))  # 0이 출력됨 (경로 압축으로 인해 2의 루트가 0이 됨)