[Python] union-find

union-find란?

- 서로소로 이루어진 부분 집합들의 상관관계를 이용하여 효율적인 상관관계(각 집합 별 루트 노드를 갖도록)를 이루도록 하는 알고리즘

- union 연산 : 연결된 노드를 확인해 하나의 집합(트리)로 합치는 연산

- find 연산 : 각 집합이 어떤 값과 연관되어 있는지 찾는 연산(루트 노드를 찾아주는 연산)

- find 연산을 집합의 정의로 해석하면 어떤 집합에 속해있는지 찾아주는 연산이라 정의 가능

 

추상적 구현

- union 함수는 두 원소를 값으로 갖는다. 인수로 받은 원소들을 find 함수를 이용해 루트 노드의 값을 얻고, 크기 비교를 통해 값을 갱신. (ex - [1, 4]의 값을 입력받았는데 4의 루트 노드가 2라면, 1과 2를 연결해주기 위해 tree[2] = 1 연산)

- find 함수는 재귀적으로 구현하는데, 자기 자신이 루트 노드가 아닐 경우 루트 노드 값을 return할 때까지 갱신

 

# PYTHON CODE

class union_find:

    def find(self, parent, x):  # parent는 초기의 parent 배열, x는 부모노드를 찾고자하는 값
        if parent[x] != x:
            return self.find(parent, parent[x])
        return parent[x]

    def union(self, parent, a, b):  # a, b는 연관을 갖도록 처리하는 값
        a = self.find(parent, a)
        b = self.find(parent, b)
        if a < b:
            parent[b] = a
        else:
            parent[a] = b