union find 알고리즘 최적화 -경로압축과 rank union-

1. 기본 union find 알고리즘의 문제점

 

기본적인 union find 알고리즘을 사용할 경우 union을 수행하면.. 예를 들어 최악의 경우 

 

 

위와 같은 union이 형성될 수 있다.

 

1의 대표자를 찾을 때, 2번, 3번, 4번을 확인하고 나서야 5번을 확인하여 1의 대표자가 5이구나 라는 것을 알 수 있다

 

이렇게 구성되는 경우 노드의 개수가 v개이고 간선의 개수가 m개이면 최악의 경우 O(VM)이라는 비효율적인 알고리즘이 된다.

 

특히 모든 1,2,3,4,5의 루트 노드가 5번인데 굳이 하나씩 거슬러 올라가서 전부 확인해야하나?

 

 

union 그래프가 위와 같이 구성된다면, 2,3,4의 루트 노드는 단 1번만 5를 검사하면 바로 알 수 있으므로 효율적이다.

 

 

2. 경로압축(path compression)

 

find함수를 재귀적으로 호출하고 나서 부모 테이블 값을 갱신하는 기법이다.

 

x의 루트를 찾으면, x의 부모를 루트로 갱신하는 방법이다.

 

##path compression

##find함수를 호출하고 바로 부모 테이블을 갱신함

def find_parent(parent,x):
    
    if parent[x] != x:
        
        parent[x] = find_parent(parent,parent[x])
    
    return parent[x]


"""기본함수와 비교

def find_parent(parent,x):
    
    if parent[x] != x:
        
        return find_parent(parent,parent[x])
    
    return x
"""

 

 

반복문으로 구현한다면.. 아마 다음과 같을 것이다(확실하진 않은데 일단 동작은 함..?)

 

동작은 하는데 효율이 조금 떨어진다.. 

 

##반복문 구현 path compression

def find_parent(parent,x):
    
    while parent[x] != parent[parent[x]]:
        
        parent[x] = parent[parent[x]]
    
    return parent[x]
    
"""기본 함수와의 비교
def find_parent(parent,x):
    
    while x != parent[x]:
        
        x = parent[x]
    
    return x
"""

 

 

 

해당 노드의 루트 노드가 바로 부모 노드가 되게 만드는 것이 핵심이다.

 

예를 들어 {1,2,3,4,5}에서 (4,5), (3,4), (2,3), (1,2)를 union하면 경로 압축을 하지 않을 때와 경로 압축을 할때 비교해보면..

 

 

 

3. union by rank

 

union 함수를 최적화할 때, i번 노드를 루트로 하는 서브트리의 높이를 rank라고 하여 rank 리스트를 parent와 같이 만든다.

 

그리고 union함수를 수행할때, rank가 낮은 집합을 rank가 높은 집합에 합치면 시간 복잡도를 어느정도 더 개선할 수 있다고 함

 

rank가 서로 다르면 문제가 없는데 rank가 동일한 경우에 두 집합을 병합하면, 다음과 같이 rank가 증가하게 된다

 

 

 

a,b의 대표자를 찾고 a,b의 rank를 비교한다.

 

rank가 낮은 집합의 부모 노드를 rank가 높은 집합의 노드 번호로 만든다.

 

그런데, rank가 서로 동일한 경우에는 rank를 1 증가시켜준다.

 

## rank by union

def union(parent,a,b):
    
    a = find_parent(parent,a)
    b = find_parent(parent,b)

    #if a == b: #루트 노드가 동일하면, 동일한 집합.. 이건 안해도 될듯?
    #    return

    if rank[a] > rank[b]: ##rank가 낮은 집합을 rank가 높은 집합 밑에 붙입니다.
        
        ##rank가 낮은 집합 b의 부모를 rank가 높은 집합 a의 노드 번호로 
        parent[b] = a
    
    else:  ##rank[a] <= rank[b]
        
        ##rank가 낮은 a의 부모를 rank가 높은 b로
        parent[a] = b

        if rank[a] == rank[b]: ##특히 rank가 서로 동일하다면
            rank[b] += 1 ##rank를 1 증가시킵니다.

 

rank 배열을 쓰지 말라고 하면 다음과 같이 가능하다.

 

항상 작은 값 기준으로 혹은 항상 큰 값 기준으로 합치면 트리의 높이가 낮아지면서 시간이 빨라지는 효과가 있다.

 

def union(parent,a,b):
    
    ##a,b의 대표자를 찾고
    
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    
    if parent[a] < parent[b]:
       
        parent[parent[a]] = parent[b] ##부모가 작은 값의 부모의 부모를 부모가 큰 값으로?
    
    else:
        
        parent[parent[b]] = parent[a]

 

4. 최적화를 적용한 union find 알고리즘

 

union find 알고리즘에서 union by rank와 path compression 최적화를 모두 적용한 알고리즘은..

 

##path compression
##반복 구조를 이용한 find함수
##원소 x의 대표자를 찾는다

def find_parent(parent,x):
    
    while parent[x] != parent[parent[x]]:
        
        parent[x] = parent[parent[x]]
    
    return parent[x]

"""##재귀로 구현한 find

def find_parent(parent,x):
    
    if x != parent[x]:
        
        parent[x] = find_parent(parent,parent[x])
    
    return parent[x]"""


##union by rank

def union_parent(parent,a,b):
    
    #a,b의 대표자를 찾는다
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    
    ##rank가 낮은 집합의 부모를 rank가 높은 집합의 노드 번호로
    ##부등호를 어떻게 설정하느냐에 따라, 어떤 것이 최종 루트가 될지 달라지니 생각을 잘 해야함
    ##얘는 근데 그냥 안하는게 좋겠는데??
    ##루트를 설정하는게 마음대로 안되는데.. 허허

    if rank[a] > rank[b]:
        
        parent[b] = a
    
    else:
        
        parent[a] = b

  ##rank가 서로 동일하면, rank를 1 증가
        if rank[a] == rank[b]:
            
            rank[b] += 1

v,e = map(int,input().split())

parent = [0]*(v+1)

##node i의 높이를 저장할 rank
##초기 rank는 1로 하는 사람도 있는듯?
rank = [0]*(v+1) ##rank를 저장할 초기화된 리스트 

##초기에 부모 테이블을 자기 자신으로 설정함
for i in range(1,v+1):
    
    parent[i] = i

##union 연산을 수행

for i in range(e):
    
    a,b = map(int,input().split())
    union_parent(parent,a,b)

##각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end = '')
for i in range(1,v+1):
    
    print(find_parent(parent,i),end= ' ')

print()

##부모 테이블 출력

print('부모 테이블: ', end='')

for i in range(1,v+1):
    
    print(parent[i],end=' ')


"""
6 4
1 4
2 3
2 4
5 6
각 원소가 속한 집합: 4 4 4 4 6 6 
부모 테이블: 4 4 4 4 6 6 
"""

 

union by rank하면, rank에 따라 부모, 자식이 결정되어가지고 루트가 생각한대로 안나올 수가 있는데

 

부등호를 잘 바꿔서 결정해야할듯?? 근데 그래도 작은 번호대로 잘 안나오던데

 

일단 웬만하면 path compression을 먼저 고려하고

 

그래도 시간을 빠르게 해야할것 같으면 union by rank도 고려하는데 node 번호가 까다로울것 같다 아무튼간에

 

 

5. 시간복잡도

 

경로압축 방법만을 이용할 경우 노드의 개수가 V개이고, 최대 V-1개의 union연산과 M개의 find 연산이 가능할 때

 

$O(V+M(1+log_{2-M/V} V))$라는 것이 알려져있다

 

예를 들어 노드의 개수가 1000개이고 union, find연산이 100만번 수행된다면 대략 1000만번 정도 연산이 필요하다고 함

 

경로 압축만큼은 개념과 구현이 간단하기 때문에 코딩테스트를 위해서 반드시 기억할 필요가 있다.

 

 

6. 참조

 

 

[알고리즘] Union-Find 알고리즘 (tistory.com)

[알고리즘] Union-Find 알고리즘

 

 

 

Union Find (velog.io)

Union Find