Python을 이용한 유니온-파인드 알고리즘의 이해와 구현

유니온-파인드 알고리즘, 또는 분리 집합(disjoint-set) 알고리즘은 집합 간의 합집합과 원소의 소속 집합을 찾는 연산을 효율적으로 수행하는 데이터 구조입니다. 이 알고리즘은 그래프의 연결성을 검사하거나 최소 신장 트리를 구하는 등의 다양한 문제에서 널리 사용됩니다. Python을 통해 이 알고리즘을 구현하고 사용하는 방법을 소개하겠습니다.

 

 

유니온-파인드 알고리즘의 기본 연산

• Find: 원소가 속한 집합의 루트 원소를 찾습니다. 루트 원소는 해당 집합의 대표 원소로, 집합의 식별자 역할을 합니다.
• Union: 두 집합을 하나의 집합으로 합칩니다. 일반적으로 두 트리의 루트를 연결하는 방식으로 집합을 합칩니다.

유니온-파인드 알고리즘의 구현

• Python에서는 클래스를 정의하여 유니온-파인드의 구조와 메서드를 구현할 수 있습니다. 아래의 예제는 path compression과 union by rank 최적화를 적용한 유니온-파인드 구현입니다.

class UnionFind:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.rank = [1] * size

    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])  # Path compression
        return self.root[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.root[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1

    def connected(self, x, y):
        return self.find(x) == self.find(y)

# 사용 예
uf = UnionFind(10)
uf.union(1, 2)
uf.union(2, 5)
uf.union(5, 6)
uf.union(6, 7)
uf.union(3, 8)
uf.union(8, 9)

print("Connected (1, 7):", uf.connected(1, 7))  # True
print("Connected (1, 3):", uf.connected(1, 3))  # False

 

 

유니온-파인드 알고리즘의 응용

• 유니온-파인드 알고리즘은 네트워크 연결, 그래프의 사이클 검출, 이미지 처리에서 객체 분할, 다양한 클러스터링 알고리즘 등에서 사용됩니다.
• 예를 들어, 최소 신장 트리 알고리즘인 크루스칼(Kruskal) 알고리즘은 유니온-파인드 알고리즘을 사용하여 간선을 추가할 때 사이클을 형성하는지 여부를 판단합니다.

Python을 사용한 유니온-파인드 알고리즘은 간단하면서도 강력한 도구로, 복잡한 네트워크 구조와 데이터 집합을 효과적으로 관리할 수 있습니다. 이 알고리즘의 구현과 활용은 효율적인 데이터 구조 및 알고리즘 설계에 중요한 기초가 됩니다.