[Algorithm] Union Find

 

Union Find 문제 상황

N개의 정점 ( 0 ~ V-1 ) 이 주어졌을 때 두 정점 a, b ( 0<=a<V, 0<=b<V) 를 연결하는 경로가 존재하는지 파악하는 문제

- Union(a, b) : 점 a와 b를 간선으로 연결한다. 
- Connected(a, b) : a와 b를 연결하는 경로가 존재하는지 T/F로 응답

 

Union Find algorithm

1. Quick Find

union과 connected를 수행하기 위해서는 그래프의 연결 상태가 필요하다. 그래프의 연결 상태를 저장하는 가장 쉬운 방법인 Adjacent List  방식으로 그래프를 저장해보겠다. 

이렇게 표현하면 장점이 개별 간선 정보를 가지고 있을 수 있다. ( 각각 간선이 어디를 연결하고 있는지 알 수 있다)

이 상태에서 Union을 하면 어떻게 구현하면 될까? 단순하다. 그냥, 인접 리스트에 정보를 추가하기만 하면 된다.

하지만, Connected 에서 큰 문제가 생긴다. 위 그림에서 Connected(0,2)가 T인지 F인지 파악하려면 0 -> 1 -> 2 과정으로 서로 연결되어 있는지 파악해야한다. 결국 평균적으로 모든 Edge 와 Vertex를 탐색해야하기 때문에 ~V+E 정도의 시간복잡도가 나온다. 매우 비효율적이다. 

	Union	Connected	Space
AdjList	~1	~V+E	~V+E

 

하지만 우리가 구현하고자 하는 Union과 Connected는 개별 간선 정보를 가지고 있지 않아도 된다. 각 객체가 어떤 덩어리에 연결되어 있는지 알고 있기만 하면 된다. 

이 연결된 덩어리를 connected component라고 한다. 예전에 strongly connected component 할 때 한 번 언급했었는데 connected component는 서로 연결된 객체들의 maximal 한 집합을 의미한다. 

Union Find를 구분하는 첫 번째 알고리즘인 Quick Find는 단순히 각 객체가 어느 connected component에 속하는지 배열에 기록하고 업데이트 할 것이다. 

 

핵심 알고리즘

1. 변수 정의 및 자료구조 초기화

• 길이 V인 정수 배열  ids[] : 각 객체가 어느 connected component에 속하는지 기록
• ids[i] : i가 속한 component의 id
• component id : component에 속한 객체 중 가장 작은 번호를 부여함. 
• ids[x] = x 로 초기화 한다. ( 아무것도 연결되지 않으면 connected component는 자신밖에 없어서 )

2. Union(a, b)

• ids[i] == ids[b]인 모든 i에 대해 ids[i] = ids[a]로 변경 ( 또는 a, b 반대로 실행 )

3. Connected(a, b)

• ids[a] == ids[b] : True 
• else False

 

 

시간복잡도 분석

union(0,3), union(0,1), union(2,4), union(4,5)를 해보면 아래와 같이 된다.

여기까지는 union 과정에서 새로 추가된 간선의 번호만 변화시키면 되기 때문에 연산량이 작다.

이 시점에서 union(1, 4)를 해보자.

이전과는 다르게, ids의 값이 2인 값을 모두 찾아서 0으로 변경해야한다. 

 

이 과정을 일반화해서 생각하면, 초반 union작업도 결국 ids을 전부 순회하면서 변경해야하는 값을 모두 찾아야 한다. 즉, union 과정의 시간복잡도는 ~V가 된다. ( V : 노트의 개수 )

하지만, Find 하는 것은 매우 쉽다. 배열의 값을 읽으면 되기 때문에 상수시간이 소요된다. 따라서 Connected 의 시간복잡도는 ~1 이다.

 

	Union	Connected	Space
AdjList	~1	~V+E	~V+E
Quick Find	~V	~1	~V

 

코드

코드로 나타내면 시간복잡도가 왜 Union은 ~V, Connected는 ~1이 나오는지 명확하게 보일 것이다.  

# Quick Find

V = 6 # 간선개수

ids = [x for x in range(V)]

def connected(a, b): 
	return ids[a] == ids[b] # ~1

def minMax(a, b):
	if a < b:
    	return a, b
    else:
    	return b, a

def union(a, b):
	id1, id2 = minMax(a, b)
    for i _ in enumerate(ids): # ~V
    	if ids[i] == id2:
        	ids[i] = id1

 

Quick Find의 장점은 Connected 가 굉장히 빠르다는 것이다. 하지만, 너무 Union이 느리다. 이를 해결하기 위해 Quick Union 방법이 나왔다. 

 

 

 

2. Quick Union

Quick Union은 connected component를 사용한다는 개념 자체는 Quick Find와 동일하다. 하지만 다른 점은 Connected component를 tree 형태로 다룬다는 것이다. 

 

union을 할 때는 root를 붙이면서 시간을 단축한다. 

이렇게 되면 connected를 수행할 때 약간 과정이 달라져야한다. Quick Find는 숫자가 같으면 같은 connected component였지만, 지금은 자신의 root를 비교해야한다. 

root는 ids[x] == x인 경우이다.

위 그림에서 connected(1, 5)를 해보자.

ids[1] = 0 -> ids[0] = 0 == 0 ( root = 0 )
ids[5] = 3 -> ids[3] = 0  -> ids[0] = 0 == 0 (root = 0)

즉, 두 개의 root가 0으로 같으니 connected의 결과는 True이다. 

 

핵심 알고리즘

1. 자료구조 정의 및 초기화

• connected component를 tree 형태로 봄
• ids[i] : 객체 i 의 parent
• ids[i] == i 이면 root
• root(i) = ids[ids[ ... ids[i] ...]]

2. union(a, b)

• root(a)를 root(b) 아래로 붙이기

3. connected(a, b)

• root(a) == root(b) : True
• else False

 

코드

# Quick Union

V = 6 # V는 간선의 개수

ids = [x for x in range(V)]

def root(i):
	while i != ids[i]: i = ids[i]
    return i
    
def connected(a, b):
	return root(a) == root(b)

def union(a, b):
	id1, id2 = root(a), root(b)
	ids[id1] = id2

 

시간복잡도 분석

union 함수만 살펴보면, Quick find와 다르게 반복문이 없기 때문에 훨씬 효율적으로 보인다. 하지만, 여기에는 함정이 있다. 바로 root를 찾는 시간을 고려하지 않았다는 것이다. 

일반적으로 균형 잡힌 tree에서는 큰 문제가 되지 않는다. 하지만, 문제는 치우친 상태의 tree이다. 

왼쪽 tree의 5번 노드는 root를 찾는데 5번이나 거슬러 올라가야하는 반면, 오른쪽 tree는 2번만에 찾을 수 있다. 간단한 사례에서도 2배 이상의 시간이 차이가 나게 된다. 

즉, Root를 찾는 과정이 최악의 경우 ~V만큼 시간이 소요된다. 

그래서 root 함수를 사용하는 union, connected 모두 느리게 작동하는 최악의 상황이 펼쳐진다. 

	union	connected	space
AdjList	~1	~V+E	~V+E
Quick Find	~V	~1	~V
Quick Union(최악인 경우)	~V	~V	~V

 

이를 해결하기 위해 다음 알고리즘인 Weighted Quick Union이 탄생했다. 

 

3. Weighted Quick Union

Quick Union의 가장 큰 문제는 Tree가 불균형할 때 root를 찾는 시간복잡도가 굉장히 높아진다는 것이다. 그래서 Union 과정에서 Tree의 크기를 계산해서 붙일 것이다. 

이때, Tree의 크기에 대해 확실히 정의하고 넘어가자

Tree의 크기는 트리에 속한 노드(객체) 수라고 하자. Weighted QU의 경우 트리의 크기를 고려해 트리를 생성하기 때문에 더 큰 트리일 수록 depth도 깊어진다. 

 

두 가지 경우를 비교해보자.

1. 큰 트리 밑에 작은 트리 붙이기
2. 작은 트리 밑에 큰 트리 붙이기

이때, 큰 트리의 높이를 dp, 작은 트리의 높이를 dq라고 하고 dp >dq 일 때라고 가정하자.

큰 트리 밑에 작은 트리가 붙으면 새로 생성된 트리의 깊이는 dp가 된다. 반대로 작은 트리 밑에 큰 트리가 붙으면 dp + 1이 된다. 트리의 깊이가 깊어지지 않게 하려면 큰 트리 밑에 작은 트리가 붙으면 된다. 

트리의 깊이가 같은 경우에는 어쩔 수 없이 1이 증가하게 된다. 하지만, 그 상황을 제외하고는 트리의 깊이가 깊어지지 않기 때문에 root 함수의 속도가 매우 빨라지게 된다. 

 

코드

# Weighted Quick Union

V = 6 # Vertex의 수

size = [ 1 for _ in range(V) ] # tree의 크기 ( 자신을 포함한 child의 개수 )
ids = [ x for x in range(V) ]

def root(i):
	while i != ids[i]: i = ids[i]
    return i

def connected(a, b):
	return root(a) == root(b)

def union(a, b):
	id1, id2 = root(a), root(b)
    if id1 == id2: # 이미 연결되어 있음.
    	return 
    
    if size[id1] < size[id2]:
    	ids[id1] = id2
        size[id2] += size[id1]
    else:
    	ids[id2] = id2
        size[id1] += size[id2]

 

시간복잡도 분석

그럼 이런 방식으로 과연 root를 찾는 부분의 시간복잡도가 해결되었을까?

시간복잡도가 해결되었는지 확인하려면 tree의 깊이가 낮아졌다는 것을 증명하면 된다. 결론적으로 Weighted QU는 log2(N)으로 깊이가 제한된다. 

증명과정

 

V개 객체 중 임의의 정점을 x라 하자.

x의 깊이가 +1이 되는 경우는 x가 속한 트리가 작을 때이다. 
이때 x가 속한 tree의 크기는 최소 2배가 된다. 

V개가 있을 때, 2배가 되면서 증가하는 경우는 많아야 log2(V)회이다. 

x의 깊이가 d번 1씩 증가한다고 가정하면
x가 속한 트리의 크기는 최소 2^d이다.

전체 그래프의 객체가 V개 밖에 없으므로 2^d <= V
따라서, d <= log2(V)이다. 

 

그래서 root의 과정이 log2(V)로 줄었다. 

	union	connected	space
AdjList	~1	~V+E	~V+E
Quick Find	~V	~1	~V
Quick Union	~V	~V	~V
Weighted Quick Union	~log(V)	~log(V)	~2V

 

 

정리

오늘은 Union Find 문제를 해결하는 방법에 대해 알아보았다. 단순히 Connected component로 묶어서 판단하는 Quick Find는 union이 너무 느리다는 단점이 있었다. 그래서 이를 해결하기 위해 connected component들을 tree로 나타내 연결하는 Quick Union을 알아보았으나, 이는 편향된 tree 때문에 최악의 경우 union과 connected 모두 성능이 좋지 않은 문제점이 발생했다. 그래서 tree의 깊이를 최소로 유지하는 시스템을 적용한 Weighted Quick Union까지 알아보았다.