유니온 파인드 알고리즘

유니온-파인드(Union-Find) 알고리즘은 집합(disjoint-set)을 효율적으로 표현하고 관리하는 알고리즘입니다. 주로 여러 개의 원소들이 속한 집합을 표현하고, 두 집합을 합치거나 어떤 원소가 어느 집합에 속해 있는지 판별하는 데 사용됩니다.

유니온-파인드 알고리즘은 트리 구조를 사용하여 각 집합을 표현하며, 두 가지 기본 연산인 "합집합(Union)"과 "찾기(Find)"를 지원합니다.

 

트리 형태로 표현하는 이유는 만약 재귀로 뿌리를 계속 찾다보면 시간이 오래걸린다. 따라서 자신의 뿌리의 가장 상위 뿌리를 자기의 뿌리로 표현하면 시간 복잡도가 줄어들기 때문이다.

 

우선 코드는 

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * 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

MakeSet(x): 원소 x를 자신만으로 하나의 집합으로 만듭니다. 이는 각 원소를 각각의 단일 노드로 나타내는 과정입니다.

parent[]테이블을 만들어 자기의 뿌리를 일단 자기 자신으로 초기화 해준다.

rank은 자신의 뿌리의 대한 깊이로, 0이면 본인 자신이 뿌리인 것이다.

Find(x): 원소 x가 속한 집합을 찾습니다. 이 때, 집합을 대표하는 루트(root)를 반환합니다. Find 연산은 경로 압축(Path Compression)을 사용하여 트리의 높이를 최소화하여 효율성을 향상시킵니다.

Union(x, y): 두 원소 x와 y가 속한 두 집합을 합칩니다. 이를 위해서 두 집합의 대표 원소(루트)를 찾아서 한 루트를 다른 루트의 자식으로 만듭니다.

 

참고 글:https://chiefcoder.tistory.com/55