서로소 집합알고리즘으로서 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.
Union-find로도 알려진 해당 자료구조는, 그래프 자료구조에서 주어진 노드간의 연결성을 효율적으로 파악할 수 있게 해준다. 즉 네트워크에서 두 요소간의 연결성을 보여주는 용도로 사용되는 것이다.
예를 들어 사회적 관계에서 두 사람이 서로 같은 조상을 가지고 있는지, 혈연관계인지에 대한 관계성을 측정할 수 있게 된다.
각 노드들의 부모와 루트 노드를 찾아서(find), 합쳐주고(union) 연결관계를 찾는 것이다.
서로소 집합에서는 각 원소들이 하나의 집합에만 속하게 된다.
이러한 특징을 통한 자료구조를 사용하면 역으로 서로 다른 두개 이상의 원소가 같은 집합에 속해있는 지 아닌 지를 판별할 수 있다.
그래서 특히 그래프 형태의 자료구조에서 두개의 요소가 연결되어있는지 아닌지를 판단할 수 있는 방법으로 활용될 수 있는 것이다.
우선 어떻게 disjoint set data structure을 활용할 수 있는지에 앞서서 Disjoin set자료구조가 무엇이고 관련된 자료구조들은 어떤게 있을까?
해당 자료구조를 활용하기 위해서는 disjoint set union 자료구조를 만들수 있어야 하는데, disjoint set자료구조의 정의에 의하면 해당 특성을 가진 두 집합 사이에는 교집합이 없으므로, 합연산을 구하기 위해서 그냥 두 집합을 더하기만 하면 된다.
이렇게 두 집합을 합하여서 판단할 수 있다보니 Union-Find 자료구조라고도 불린다.
* Union(합치기) 연산 : 두 원소 a,b가 주어질 때 이들이 속한 두 집합을 하나로 합친다.
* Find(찾기)연산 : 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환한다.
주요 용어
parent node : 주어진 노드가 연결한 노드(방향을 가르키고 있는노드)이다. 위의 예제에서 노드 3의 부모 노드는 1이다.
root node : parent node가 없는 노드이다.
How do "disjoint set" work
위의 그림과 같이 몇개의 그래프만 있는 경우에는 바로 관계성을 파악할 수 있다. 하지만 그래프가 너무 많은 경우에는?
옆의 그림과 같이 각 요소가 주어진 경우, 오른쪽의 union에 따라서 왼쪽의 각 요소들을 묶어보자.
그리고 하나라도 엮여있으면 다 같은 하나로 묶자.
해당 자료구조는 트리구조를 이용해서 표현되는데 배열이 아니라 트리를 사용하는 이유는 무엇일까??
배열을 활용하게 되면, Union 즉 합치는 과정에서 모든 원소를 순회해야 하므로 시간 복잡도가 O(N)이 된다. 물론 이후에 특정 원소가 어느 집합에 속하는지를 찾는 Find연산은 빠르지만 실제로 Union 수행횟수가 더 많기 때문에 Unoin연산이 더 빨라야 한다.
이 때문에 배열 보다 트리 구조가 더 효율적이다. 그렇다면 트리구조로 Union-Find 연산을 어떻게 수행할 수 있을까?
disjoint set을 배열로 표현할 지, 트리로 표현할 지에 대해서는 아래에 좀 더 자세하게 설명할 예정이다
"disjoint-set" 이행하기
그렇다면 실제로 disjoint-set은 어떻게 이행되는 걸까?
프로그램으로 작성하여 컴퓨터가 이해하도록 하여 disjoint-set을 어떻게 실행할 수 있을까?
서로소집합 자료구조는 find function/ union function 이 두개의 중요한 함수의 개념을 알아야 한다.
이 두개의 함수로 서로소 집합자료구조를 조작할 수 있는 것이다.
root array에는 각 부모노드의 루트 노드를 저장할 예정이다.
index가 각 노드이며, parent 노드에는 각 노드의 실제 부모 노드를 기재한다.
find function : 주어진 노드의 루트 노드를 찾는 함수.
union function : 루트 노드가 같은 두개의 노드를 하나로 합치는 함수.
disjoint-set을 실행하는 연산
초기화: N 개의 원소가 각각의 집합에 포함되어 있도록 초기화 합니다.
quick find 실행 : 시간복잡도는 O(1)
quick union 실행 : 시간복잡도는 O(N)으로 시간이 더 걸리지만, 실행하는데 있어서 더 효율적이다.
Union 연산(합치기) : 각자 다른 집합 트리의 루트를 찾은뒤, 그 루트가 다르다면, 하나를 다른 한쪽의 자손으로 넣어 두 트리를 합친다
Find 연산(찾기) : 노드에 저장된 포인터 정보를 따라가 주어진 원소가 포함된 트리의 루트 노드를 찾는다. (이때 트리의 높이와 시간 복잡도가 비례한다.)
Union-find 연산이란
Disjoint Set을 표현할 때 사용하는 독특한 형태의 자료구조이다.
위에서 Disjoint set실행을 위한 두 연산인 union-find 연산에 대해서 언급했고 간략하게 설명했다. 그리고 이를 구현하기 위해서 배열구조보다는 트리 구조를 표현한다고 하는데 이에 대해서 좀 더 자세하게 다뤄보고자 한다.
배열로 표현하기
가장 간단한 방법으로 1차원 배열로 집합을 표현한다.
예를 들어
번 원소가 속하는 집합의 번호
Union-Find 지원 연산
초기화: 위와 같이 각자 다른 집합 번호로 초기화
Union (합치기) 연산: 두 집합을 합치기 위해 배열의 모든 원소를 순회 하면서 하나의 집합 번호를 나머지 한개의 집합 번호로 교체. 아래의 그림은3번 집합을 2번 집합으로 합치는 과정.
Find (찾기) 연산: 한 번만에 원소가 속하는 집합 번호를 알 수 있다.
배열로Union-Find를 구현 할 수는 있지만, 위에서 보았듯Union연산 수행 시 배열의 모든 원소를 순회해야 하기 때문에 시간복잡도가
이 된다. 물론Find연산은 빠르지만,Union연산 수행 횟수가 많기 때문에 우리는 더 빠른Union연산을 원한다.
트리로 표현하기
바로트리로Union-Find를 구현하면 배열보다 빠르게Union연산을 수행할 수 있다.
Base 1 한 집합에 속하는 원소들을 하나의 트리로 묶어주기 때문에, 자료구조는 아래 그림과 같이트리 들의 집합으로 표현된다.
Base 2 트리 구조에는 트리의 대표 노드 라고도 볼 수 있는루트 노드가 존재 하므로, 각 원소가 속하는 집합 번호를 바로 이루트 노드의 원소로 정함.
Base 3 Union연산을 수행하기 위해서는 두 원소가 같은 집합에 속하는지를 먼저 확인한 후, 다른 집합에 속할 때만 합쳐야 한다. 같은 집합에 속한다는 뜻은, 같은루트 노드를 가진다는 말과 대응되므로 어떤 원소의루트 노드를 찾는Find연산을 지원해야 한다.
Base 4 이러한Find연산을 지원하기 위해서 모든 자식 노드가 부모에 대한 포인터 정보를 가지고 있도록 한다. 이러한 설정은 가진 정보를 바탕으로 포인터를 따라가 결과적으로 최종 부모인루트 노드가 무었인지 찾을 수 있게 된다. 단, 부모 노드에서 자식 노드로 내려가는 일은 발생하지 않기 때문에, 부모가 자식에 대한 포인터 정보는 가질 필요가 없다.
Union-Find 지원 연산
초기화: 모두 각자 다른 집합이 된다. 각 노드는 모두루트 노드가 되며 N 개의루트 노드를 생성하고 자기 자신을 가리키는 포인터를 가지도록 설정합니다.
Union (합치기) 연산: 각 트리의 루트를 찾은 뒤, 다르다면 하나를 다른 한쪽의 자손으로 넣어 두 트리를 합칩니다.
Find (찾기) 연산: 각 노드에 저장된 포인터 정보를 따라가 주어진 원소가 포함된 트리의루트 노드를 찾습니다. ( 트리의 높이와 시간복잡도가 비례 )
Find연산 수행 시 걸리는 시간이트리의 높이와 비례하게 되고,Union연산 수행시간 역시Find연산 수행 시간이 지배하게 된다. 이처럼Union연산시간 복잡도가 배열로 나타내었을 때의
보다 줄어 들었다.
Quick Find - Find 연산
union find를 구현한 가장 간단한 알고리즘이다. 노드가 연결될 때마다 모든 노드를 순회하면서 연결된 노드를 변경한다.
먼저 각 노드의 루트 노드들을 탐색해서 수정한 다음(union), 찾음(find - connected)
-> 노드 4의 루트 노드를 찾기 위해서 부모 노드인 1 -> 0의 방법으로 루트 노드를 찾음
-> 차례차례로 루트 노드를 찾음.
-> 그리고 각 노드의 부모노드가 아니라 루트 노드를 배열로 저장.
# UnionFind class
class UnionFind:
def __init__(self, size):
self.root = [i for i in range(size)]
# self.root = [0,1,2,3,4,5,6,7,8,9]
def find(self, x):
return self.root[x]
def union(self, x, y):
rootX = self.find(x)
# x=1, rootX = 1
rootY = self.find(y)
# y=2, rootY = 2
if rootX != rootY:
for i in range(len(self.root)):
# len(self.root) = 10
if self.root[i] == rootY:
# i = 2, self.root[2] = 2(rootY)
self.root[i] = rootX
# self.root[2] = 1
# self.root = [0,1,1,3,4,5,6,7,8,9]
def connected(self, x, y):
return self.find(x) == self.find(y)
# Test Case
uf = UnionFind(10)
# 1-2-5-6-7 3-8-9 4
uf.union(1, 2)
uf.union(2, 5)
uf.union(5, 6)
uf.union(6, 7)
uf.union(3, 8)
uf.union(8, 9)
#union함수는 연결되어있는 각 노드들을 실제로 연결해주는 역할을 한다. 1과2부터 먼저한 이유는,
#실제 연결된 서로소 집합에서 root노드가 1이므로 이를 중심으로 아래에 노드를 붙여주기 위함이다.
#위의 union함수를 다 거치고 나면
#self.root = [0,1,1,3,4,1,1,1,3,3] 이 된다.
print(uf.connected(1, 5)) # true
print(uf.connected(5, 7)) # true
print(uf.connected(4, 9)) # false
# 1-2-5-6-7 3-8-9-4
uf.union(9, 4)
print(uf.connected(4, 9)) # true
init: 모든 노드를 순회하면서 초기화하고, N개의 데이터를 저장할 수 있는 메모리가 필요하다. 시간 복잡도는 O(N)이다.
union: 모든 노드를 순회하면서 연결된 노드를 변경한다. 시간 복잡도는 O(N)이다.
그러나 find 실행은 O(1)으로 빠르다.
connected: 두 노드의 연결 여부를 확인한다. 시간 복잡도는 O(1)이다.
union 연산이 모든 노드를 순회하기 때문에 비효율적이다.
Quick Union - Union 연산
quick find 알고리즘의 union 연산을 개선하기 위한 알고리즘이다. 노드가 속한 집합을 트리 구조로 형성하고, 노드가 속한 트리의 루트 노드와 연결된 노드만 변경한다.
-> quick find에서는 모든 노드를 순회해서 root node를 동일화 한다음 find해준다. 이 과정에서 union에 O(N) 시간 복잡도가 소요된다. 하지만 quick union의 경우에는 기존의 루트 노드만 저장해놓은 다음에 find를 위해서 경로를 추적한다(traverser)
-> 실제로 코드를 보면 find와 union의 차이를 느낄 수 있다.
# UnionFind class
class UnionFind:
def __init__(self, size):
self.root = [i for i in range(size)]
# self.root = [0,1,2,3,4,5,6,7,8,9]
# self.root = [0,1,1,3,4,5,6,7,8,9]
def find(self, x):
# x=1, self.root[1] = 1
# x=2, self.root[2] = 1
while x != self.root[x]:
#이 부분이 quick find와 다른 점
#한번의 union으로 root가 결정된 노드에 대해 find->union하려 할때,
#quick find와 달리, 해당 node를 아예 root값으로 바꾸어주어서, union의 연산 시간을 줄여줌.
#이를 통해, quick find에서는 매번 union할때 for반복문을 해주어야 했지만, quick union에서는
#조건문 하나로 바로 union이 가능
x = self.root[x]
return x
def union(self, x, y):
rootX = self.find(x)
# x=1, rootX=1
# x=2, rootX=
rootY = self.find(y)
# y=2, rootY=2
if rootX != rootY:
# 즉 두개의 노드가 union되지 않은 경우,root를 기준으로 union해주기 위해
self.root[rootY] = rootX
# self.root[2] = 1, self.root=[0,1,1,3,4,5,6,7,8,9]
def connected(self, x, y):
return self.find(x) == self.find(y)
# Test Case
uf = UnionFind(10)
# 1-2-5-6-7 3-8-9 4
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(uf.connected(1, 5)) # true
print(uf.connected(5, 7)) # true
print(uf.connected(4, 9)) # false
# 1-2-5-6-7 3-8-9-4
uf.union(9, 4)
print(uf.connected(4, 9)) # true
init: 모든 노드를 순회하면서 초기화하고, N개의 데이터를 저장할 수 있는 메모리가 필요하다. 시간 복잡도는 O(N)이다.
root: 노드가 속한 트리의 루트 노드를 반환한다. 시간 복잡도는 O(N)이다.
union: 노드가 속한 트리의 루트 노드와 연결된 노드만을 변경한다. 시간 복잡도는 O(N)이다.
connected: 두 노드의 연결 여부를 확인한다. 시간 복잡도는 O(N)이다.
connected 연산의 시간 복잡도는 증가하였으나, union 연산이 모든 노드들을 순회하지 않고 변경이 필요한 노드만 변경한다.
