2 Apr 2019 • on data structure, algorithm, tree

파이썬 자료구조 (6) Disjoint Set

아래 포스트는 Data Structure and Algorithmic Thinking with Python을 참고하여 작성되었습니다.

1) Disjoint Set

1-1. 소개

Set : 원소들을 나타내는데 ordering이 필요하지 않은 경우

매우 구현하기 쉬움, 다른 알고리즘의 재료격 구조로 사용된다.

우리는 Set을 정의역으로 하는 어떤 relation R을 정의할 수 있는데,

이 Relation이 equivalence relation이 되기 위해서는 reflexive, symmetric, transitive가 성립해야 한다.

이런 R에 대해서 equivalence class들을 만들 수 있는데, 이런 class들은 하나의 set을 분할하기 때문에 이걸 가끔 Disjoint-Set으로도 부른다.

1-2. Operation

Making a set
Find(X) : 원소 X를 포함하는 set을 찾는다.
Union(X, Y) : 원소 X와 Y를 포함하는 새로운 set을 만들고, 기존에 X와 Y를 포함하는 set을 제거한다.

1-3. Application

네트워크 연결구조를 표현하기 위해
lowest common ancestor : 트리에서 두 노드 w, v를 자식으로 가지는 가장 깊은(level이 낮은) 조상노드

-> 왜 유용한가? : 두 노드 w, v사이의 거리를 구할 수 있기 때문?

-> 왜 set을 이용하는가 ? : w ~ root path와 v ~ root path의 교집합을 구하면 되기 때문.
Kruskal의 MST 알고리즘을 이용하기 위해

1-4. Tradeoffs in Implementing Disjoint Sets ADT

Find/Union 연산을 시행하는 방식은 두가지가 있다.

두 가지는 방식은 서로 Tradeoff가 있기 때문에 장단점을 잘 이해하는게 중요하다.

Quick Find

Array를 이용함.

Array의 각 원소는 set name을 뜻함

=> 특정 원소가 어떤 set에 들어가있는지를 찾기 위해서는 오직 인덱스 참조만 하면 되므로 O(1)의 시간복잡도임.
Union(a, b) 연산 : b의 set name을 가지고 있는 모든 array의 원소들에 대해서 a의 set name으로 바꿔주면 되므로 O(n)이다.

구현예시)

class Set:
   
    def __init__(self, N):
        self.S = list(range(1, N+1))
        self.max = N
        self.size = N
   
    def find(self, i):
        return self.S[i]
   
    def union(self, i, j):
        i_num, j_num = self.find(i), self.find(j)
        if i_num != j_num:
            for k in range(self.max):
                if self.find(k) == j_num:
                    self.S[k] = i_num
            self.size -= 1

Quick Union

여러 가지 방법이 있다

Quick Union with Slow Find

각 set을 tree(set name = root 원소의 이름)구조로 만들 수도 있다.

Union(X, Y)
1. X트리와 Y트리를 포함하는 최대의 Component(A, B로 통칭)를 찾는다. (ROOT를 찾으면 됨)
2. A트리의 직계자식으로 B트리를 추가한다.
Find(X)
1. X트리의 ROOT를 찾는다.

=> 추가하는거 자체는 O(1)이지만 Union에 Find연산이 동반되므로 skewed-tree의 경우에는 시간복잡도가 O(n)까지 될 수 있음.

구현예시

class Tree:
    def __init__(self, i):
        self.data = i
        self.parent = None
      
    def __str__(self):
        return f"Tree[data = {self.data}, parent = {self.parent}]"
      
class Set:
    def __init__(self, N):
        self.S = [Tree(i) for i in range(N)]
        self.size = N
      
    # 루트노드를 찾는 메서드
    def find(self, i):
        tree = self.S[i]
        while tree.parent:
            tree = tree.parent
        return tree
      
    def union(self, i, j):
        i_tree = self.find(i)
        j_tree = self.find(j)
        if i_tree.data != j_tree.data:
            j_tree.parent = i_tree
            self.size -= 1

Quick Union with Quick Find

1번의 단점은 skewed-tree의 경우에 비효율적이라는 점인데, 이걸 극복하기 위한 두 가지 방법이 있다.

Union by Size

Set의 표현방식
1. root인 element x : -x로 표현
2. root가 아닌 element x : 부모노드의 인덱스로 표현
MAKESET : Array형식으로 set number를 저장한다.

(전부 root이기 때문에 전부 -1로 저장합니다.)
FIND(X)
1. Set[X]가 음수이다 -> 음수는 루트노드이므로, 찾았다!
2. Set[X]가 음수가 아니다 -> 값은 부모의 인덱스를 의미하므로,
  
  FIND(FIND(Set[X]))은 부모노드의 인덱스를 다시 넣어서 재귀적으로 Set을 찾겠다는 뜻이다.
Union(root1, root2)

set의 root를 find연산으로 찾았다는 가정하에 진행한다.

root1에 딸린 사이즈가 크다고 가정하면,

Set[root1] <- Set[root1] + Set[root2]

Set[root1] <- Set[root2]

이런식으로 두개만 조절하면, 자식노드를 만들어 줄 수 있다.

ex) [2 2 -3 -1 -1 6 -2]

Union(2, 6) => [2 2 -5 -1 -1 6 2]

즉, 2번 루트노드는 0, 1, 6번 자식노드를 가지며,

6번 노드 역시 5번 자식노드를 가지는 것으로 해석할 수 있다.

class Set:
    def __init__(self,N):
        self.S = [-1 for _ in range(N)]
        self.size = N
        
    # find의 결과값 : 루트노드의 인덱스
    def find(self, i):
        set_num = self.S[i]
        if set_num < 0:
            return i
        else:
            return self.find(set_num)
        
    def union(self, i, j):
        """
        1. 루트노드의 인덱스를 찾는다.
        2. 루트노드의 인덱스가 다르다면,
            - 리스트의 값이 더 낮은(size가 더 큰) 것을 찾아서
            큰 것에 더해준다.
            - 작은건 큰것의 인덱스로 바꿔준다.
        """
        i_root = self.find(i)
        j_root = self.find(j)
        if i_root != j_root:
            if self.S[i_root] < self.S[j_root]:
                self.S[i_root] += self.S[j_root]
                self.S[j_root] = i_root
            else:
                self.S[j_root] += self.S[i_root]
                self.S[i_root] = j_root
            self.size -= 1

Union by Height

Union by Size와 로직은 비슷합니다.

Union by Size는 두 트리를 결합할 때 트리의 size가 큰 순서대로 집어삼켰다면,

이 알고리즘은 height가 큰 순서대로 집어삼킨다고 생각하면 됩니다.

시간복잡도 분석

Union by Size

(1) 각 트리의 높이는 기껏해야 logN을 넘지 못한다

왜냐하면 높이가 하나 증가할 때 마다

작은 트리는 큰 트리에 속하게 되므로, Size는 두배 이상 증가하기 때문입니다.

=> 따라서 Find연산은 기껏해야 O(logN)의 소모값을 가집니다.

(2) 물론 Union도 Find연산을 해야하므로 똑같이 생각하면 됩니다.
Union by Height

역시 높이는 기껏해야 logN을 넘지 못합니다.
1. 같은 높이의 트리 두개를 Union : 1 증가
2. 다른 높이의 트리 두개를 Union : 두 트리 중에서 큰 높이로 설정됨

class Set:
        
    def __init__(self,N):
        self.S = [-1 for _ in range(N)]
        self.size = N
        
    # find의 결과값 : 루트노드의 인덱스
    def find(self, i):
        set_num = self.S[i]
        if set_num < 0:
            return i
        else:
            return self.find(set_num)
        
    def union(self, i, j):
        """
        1. 루트노드의 인덱스를 찾는다.
        2. 루트노드의 인덱스가 다르다면,
            -
        """
        i_root = self.find(i)
        j_root = self.find(j)
        if i_root != j_root:
            if self.S[i_root] < self.S[j_root]:
                self.S[j_root] = i_root
            elif self.S[i_root] > self.S[j_root]:
                self.S[i_root] = j_root
            else:
                self.S[i_root] -= 1
                self.S[j_root] = i_root
            self.size -= 1

Path Compression

Find Operation 을 실행한 뒤에

더 효과적으로 찾을 수 있게끔 트리를 재구성하는 방식이 있다고 합니다.

방식

Find(X)를 실행한다.
X가 루트노드가 아니라면 임시로 저장한다.
루트노드를 찾을 때 까지 거슬러 올라간다.
루트노드를 찾으면 X를 루트노드의 자식으로 직접적으로 매겨준다.

구현예시

class Set:
    size = 0
      
    def __init__(self,N):
        self.S = [-1 for _ in range(N)]
        Set.size = N
      
    # find의 결과값 : 루트노드의 인덱스
    def find(self, i):
        to_change = []
      
        def upward(i):
            set_num = self.S[i]
            if set_num < 0:
                return i
            else:
                to_change.append(i)
                return upward(set_num)
      
        res = upward(i)
        for e in to_change:
            self.S[e] = res
        return res
      
      
    def union(self, i, j):
        i_root = self.find(i)
        j_root = self.find(j)
        if i_root != j_root:
            if self.S[i_root] < self.S[j_root]:
                self.S[j_root] = i_root
            elif self.S[i_root] > self.S[j_root]:
                self.S[i_root] = j_root
            else:
                self.S[i_root] -= 1
                self.S[j_root] = i_root
            Set.size -= 1

DongChanS's blog