서로소 집합(Disjoint Set), 유니온 파인드(Union-Find)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

유니온 파인드란 서로소 집합(Disjoint Set)을 표현할 때 사용하는 알고리즘이다. 그렇다면 Disjoint Set의 정의부터 명확히 해야한다.

서로소 집합(Disjoint Set)이란?

공통 원소가 없이 "상호 배타적인" 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.

정의에서 말하는 기능을 지원하기 위해서는 다음의 세 가지 연산을 지원해야 한다.

• 초기화 : N개의 원소가 각각의 집합에 속하도록 초기화한다.
• Union(합치기) 연산 : 두 원소가 주어졌을 때 두 원소가 속한 집합을 하나로 합친다.
• Find(찾기) 연산 : 어떤 원소가 주어졌을 때 해당 원소가 속한 집합을 반환한다.

세 가지 연산 중 Union 연산과 Find 연산을 지원해야 하므로 Disjoint Set 자료구조는 Union-Find 알고리즘이라고도 불리게 된다. 따라서 두 가지 개념은 따로 논의될 수 없으므로 자료구조에는 Disjoint Set을 그걸 표현하는 알고리즘을 Union-Find 알고리즘이라 칭하면 되겠다. (유의어 정도로 간주하자.)

Union-Find 알고리즘의 구현

배열 vs 트리

Union-Find의 구현은 주로 트리 기반으로 구현한다, 그렇다면 이유를 정리해보자.

배열로 Union-Find 구현

• Array[i] : i좌표 원소가 속하는 집합의 번호라 하자.
• 초기화 : Array[i] = i로 각자 자기자신에 속하도록 초기화한다.
• Union : 두 집합을 합하기 위해 배열을 순회하면서 하나의 집합을 다른 하나의 집합 번호로 교체한다.

배열을 처음부터 끝까지 순회하므로 $O(N)$이 된다.

• Find : 해당 좌표를 검색하면 되므로 O(1)이다.

Union-Find 배열 기반 구현 python 코드

class disjointSet:
    def __init__(self, n):
        self.data = [i for i in range(n)]
        self.size = n

    def find(self, idx):
        return self.data[idx]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        for i in range(len(self.data)):
            if self.data[i] == y:
                self.data[i] = x
        self.size -= 1


s = disjointSet(10)
s.union(0, 1)
s.union(2, 3)
s.union(1, 2)
s.union(0, 1)
s.union(4, 5)
s.union(5, 6)
s.union(7, 8)
s.union(7, 9)

print(s.data)
print(s.size)

트리로 Union-Find 구현

두 개의 Disjoint Set이 있다고 하자.

노드의 구조는 단순하게 부모 노드가 누구인지만 정보를 담고 있으면 된다. 각 노드의 부모노드 정보만 가지고 있고 각 Disjoint Set 트리의 루트 노드는 루트노드임을 알려주는 지표를 갖는다. 자식 노드를 찾을 일은 없기 때문에 그에 대한 정보는 담지 않는다.

• 초기화 : 각자 다른 집합이 된다. 모두가 자기자신을 루트노드로 갖는다.

• Union : 각 트리의 루트 노드를 찾은 뒤 다르다면 한쪽 트리의 루트 노드를 다른 한 쪽의 루트 노드로 바꿔 자식으로 넣음으로써 트리를 합한다. ($O(1)$, Find 연산의 시간복잡도에 전적으로 의존)

• Find : 각 노드에 저장된 부모 노드 정보를 따라가서 자기자신을 부모로 갖는 루트 노드를 찾는다. ($O(h)$, 트리의 높이와 시간복잡도가 비례)

위 그림에 따라 트리가 최악의 경우라도 더 유리함을 알 수 있다.

Union-Find 트리 기반 구현 python 코드 - 기본형

class disjointSet:
    def __init__(self, n):
        self.data = [-1 for _ in range(n)]
        self.size = n

    def find(self, idx):
        parent = self.data[idx]
        if parent < 0:
            return idx
        return self.find(parent)

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        self.data[y] = x
        self.size -= 1


s = disjointSet(10)
s.union(0, 1)
s.union(2, 3)
s.union(1, 2)
s.union(0, 1)
s.union(4, 5)
s.union(5, 6)
s.union(7, 8)
s.union(7, 9)

print(s.data)
print(s.size)

위의 코드가 기본적인 기능만을 지원했을 때의 코드다. 여기서 조금 더 고도화하여 두 개의 Disjoint Set이 있을 때 크기가 작은 집합이 큰 집합에 더해지거나 높이가 낮은 트리가 큰 높이를 갖는 트리에 더해지는 게 균형이 맞아보인다.

Union-Find 최적화

Union 연산 최적화하기

트리로 구성했을 때 시간복잡도가 $O(log\ h)$라 했지만 BST의 경우에도 그렇고 사향트리를 형성해버린 경우 원소의 개수가 N일 때 높이가 N인 연결리스트 꼴이 되어버린다. 만약 그렇다면 Find 연산의 시간복잡도는 $O(N)$이 되어버려 배열로 구현했을 때보다 효율이 나빠진다.

이를 방지하기 위해 높이 정보를 담아 해결할 수 있다. union-by-rank라 하는데 union-by-height라고도 부른다. 번외로 union-by-size도 구현해보자.

union by size

class disjointSet:
    def __init__(self, n):
        self.data = [-1 for _ in range(n)]
        self.size = n

    def find(self, idx):
        parent = self.data[idx]
        if parent < 0:
            return idx
        return self.find(parent)

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.data[x] < self.data[y]:
            self.data[x] += self.data[y]
            self.data[y] = x
        else:
            self.data[y] += self.data[x]
            self.data[x] = y
        self.size -= 1


s = disjointSet(10)
s.union(0, 1)
s.union(2, 3)
s.union(1, 2)
s.union(0, 1)
s.union(4, 5)
s.union(5, 6)
s.union(7, 8)
s.union(7, 9)

print(s.data)
print(s.size)

union by rank(union by height)

class disjointSet:
    def __init__(self, n):
        self.data = [-1 for _ in range(n)]
        self.size = n

    def find(self, idx):
        parent = self.data[idx]
        if parent < 0:
            return idx
        return self.find(parent)

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.data[x] < self.data[y]:
            self.data[y] = x
        elif self.data[x] > self.data[y]:
            self.data[x] = y
        else:
            self.data[x] -= 1
            self.data[y] = x
        self.size -= 1


s = disjointSet(10)
s.union(0, 1)
s.union(2, 3)
s.union(1, 2)
s.union(0, 1)
s.union(4, 5)
s.union(5, 6)
s.union(7, 8)
s.union(7, 9)

print(s.data)
print(s.size)

Find 연산 최적화하기

트리의서의 Union-Find는 전적으로 트리의 높이에 의존하는데 결국 Find 연산의 시간복잡도가 개선되어야 한다. Union-Find 알고리즘에서의 Find 연산을 수행하면서 트리의 높이를 낮추는 과정을 "Path Compression(경로 압축)"이라 부른다.

• find(node) 실행
• node가 루트 노드가 아니라면 별도 공간에 임시 저장
• 루트 노드를 찾을 때까지 1, 2 재귀 반복
• 3의 결과로 루트 노드를 찾으면 임시로 저장해둔 노드들을 루트 노드의 자식으로 저장

기존 find 함수를 루트 노드를 탐색하면서 임시 공간에 저장하는 부분과 찾고 나서 경로를 압축하는 두 개의 파트로 구분해야 한다.

Path Compression 적용

class disjointSet:
    def __init__(self, n):
        self.data = [-1 for _ in range(n)]
        self.size = n

    def upward(self, buf, idx):
        parent = self.data[idx]
        if parent < 0:
            return idx
        buf.append(idx)
        return self.upward(buf, parent)

    def find(self, idx):
        buf = []
        result = self.upward(buf, idx)
        for i in buf:
            self.data[i] = result
        return result

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.data[x] < self.data[y]:
            self.data[y] = x
        elif self.data[x] > self.data[y]:
            self.data[x] = y
        else:
            self.data[x] -= 1
            self.data[y] = x
        self.size -= 1

s = disjointSet(10)
s.union(0, 1)
s.union(2, 3)
s.union(1, 2)
s.union(0, 1)
s.union(4, 5)
s.union(5, 6)
s.union(7, 8)
s.union(7, 9)

print(s.data)
print(s.size) 

Union-Find 알고리즘의 시간복잡도

Union-Find의 시간복잡도는 전적으로 Find 연산의 시간복잡도에 종속되며 Find 연산의 시간복잡도는 트리의 높이 h에 의해 결정됨을 확인하였다. 그러나 Find 연산 수행 시 Path Compression이 수행되어 트리의 높이 변화가 발생한다.

증명과정은 따로 정리해야 할 정도로 길어 결론만 말하면 union-by rank와 path compression이 모두 적용됐을 때 평균 시간복잡도는 $O(\alpha(N))$이라고 한다.

$\alpha(N)$은 애커만(Ackermann) 역함수로 매우 빠르게 증가하는 애커만 함수로부터 정의된다.

• $1 \le N < 3$인 경우 $\alpha(N) = 1$
• $3 \le N < 7$인 경우 $\alpha(N) = 2$
• $7 \le N < 63$인 경우 $\alpha(N) = 3$
• $63 \le N < 2^{2^{2^{65536}}}$인 경우 $\alpha(N) = 4$

4번째 조건의 상한은 무한에 가까운 수로 일반적인 경우 $\alpha(N) = 4$ 로 간주하여 상수와 다를 바 없다. 따라서 Union-Find 알고리즘은 상수시간에 수행이 완료되어 굉장히 빠름을 알 수 있다. 굳이 따지자면 Path Compression을 하느라 임시 공간에 저장했던 노드들을 패치하는 시간 정도를 고려할 수 있겠다.