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

Union-Find

Union - find(합집합 찾기) 알고리즘은 여러 개의 node들이 존재하고 노드들을 서로 이어 집합을 만들 때 서로 다른 노드가 같은 집합인지 확인할 때 사용하는 알고리즘입니다.

 

union - find 말 그대로 union과 find 과정을 통해 알고리즘을 수행합니다.

 

예를 들어 다음과 같이 5개의 노드들이 있다고 가정해봅시다.

 

 

1	2	3	4	5
1	2	3	4	5

1 행은 각 노드 번호

2행은 각 노드의 부모 노드 번호입니다.

 

우선 시작 시 노드들은 각자 자신을 부모로 가리키고 있고 서로 연결되어 있지 않습니다.

 

union 과정을 통해 노드 1, 4를 2, 5 를 연결해봅시다.

 

1	2	3	4	5
1	2	3	1	2

다음과 같이 숫자가 더 높은 노드가 아래 노드를 부모로 가지도록 했습니다.

 

이제 (1,4)와 (2,5)는 같은 집합 속에 있습니다.

 

여기서 노드 4와 5가 같은 집합에 존재하는 지 아닌 지 확인하려면 어떻게 해야할까요?

 

1. 각각의 노드의 부모노드를 확인한다.

2. 같은 부모노드를 가리키고 있을 경우 같은 집합에 있음을 알 수 있다.

    2-1. 같은 부모노드를 가리키지 않을 경우 서로 다른 집합에 존재한다.

 

위처럼 하나만 연결되어있는 경우 외에도 3이 5를 가리키게 되면 재귀적으로 3->5->2 순서로 최종 부모를 찾을 수 있고 서로 다른 노드가 같은 집합에 존재하는 지 아닌 지 알 수 있습니다.

 

union-find는 매우 직관적이고 쉬운 알고리즘으로 나중에 더 어려운 알고리즘의 기초가 됩니다. 따라서 쉬울 때 확실히 초석을 다지고 가는 것이 중요해 보입니다.

 

다음은 파이썬 코드입니다.

 

def get_parents(parents, node):
    if parents[node] == node:
        return node
    return get_parents(parents, parents[node])

def union_parents(parents, a, b):
    a = get_parents(parents, a)
    b = get_parents(parents, b)

    if a < b:
        parents[b] = a
    else:
        parents[a] = b

def find_parents(parents, a, b):
    a = get_parents(parents,a)
    b = get_parents(parents,b)
    if a == b:
        return True
    return False



if __name__ == "__main__":
    parents = [x for x in range(10)]        #부모 노드 
    union_parents(parents,1,4)      #node 1, 4 
    union_parents(parents,2,5)      #node 2, 5

    print("node : 4 5",find_parents(parents,4,5))
    
    union_parents(parents,1,2)      #node 1, 2
    
    print("node : 4 5",find_parents(parents,4,5))

출력