[알고리즘] 유니온 파인드(Union-Find)

유니온 파인드(Union-Find) 알고리즘이란?

"서로소 집합(Disjoint Set)을 효율적으로 관리하는 자료구조"
[서로소 집합: 공통 원소가 없는 집합]

"두 원소가 같은 집합에 속해 있는지 확인하고, 두 집합을 합치는 작업을 빠르게 수행한다."

 

주요 연산

 

1. Find(찾기)

• 어떤 원소가 속한 집단의 대표 원소(루트)를 찾는다.
• 두 원소가 같은 집단에 속해 있는지 확인할 수 있다.

 

2. Union(합치기)

• 두 집합의 루트를 찾아 하나의 집합으로 합친다.

-> 이 2가지 기법만 가지고 구현하면 트리의 깊이가 깊어질 수 있다. 매번 한 트리의 루트에 다른 트리를 연결하면 트리의 높이가 증가하여 Find 연산이 비효율적으로 수행되므로 최적화 기법이 필요하다.

 

 

최적화 기법 

 

1. 경로 압축(Path Compression): Find 연산을 할 때 모든 노드를 루트 노드와 직접 연결

                                                    -> 트리의 높이 축소-> 다음 Find 연산을 수행할 때 더욱 빠르게 루트 도달 가능

6의 부모는 4, 4의 부모는 3, 3의 부모는 1로 최종 부모는 1

 

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

 

 

2. 랭크 최적화(Union by Rank): Union 연산을 할 때 트리의 높이가 더 낮은 트리를 높은 트리에 붙인다.

                                                   -> 트리 높이의 최소화로 더 효율적인 Find 연산 가능

def union(parent, rank, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)
    
    # 두 루트가 다르다면 두 집합을 합쳐야 한다.
    if rootA != rootB:
    	# A 트리의 높이가 더 크다면 A루트 밑으로
        if rank[rootA] > rank[rootB]:
            parent[rootB] = rootA
        # B 트리의 높이가 더 크다면 B루트 밑으로
        elif rank[rootA] < rank[rootB]:
            parent[rootA] = rootB
        # 높이가 같은 경우 B를 A에 합침
        else:
            parent[rootB] = rootA
            rank[rootA] += 1 # A 트리의 높이 +1

 

 

동작 과정

1. 각 원소는 자기 자신을 부모로 가지는 트리 형태로 시작한다.

2. 두 집합의 루트를 찾고, 랭크에 따라 더 작은 트리를 큰 트리에 합친다.

 

 

구현

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]  # 각 노드의 부모를 자기 자신으로 초기화
        self.rank = [0] * n  # 각 노드의 랭크(트리의 높이)를 0으로 초기화

    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):
        rootX = self.find(x)
        rootY = self.find(y)

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