[알고리즘] union find 연산 1

Hyo Kyun Lee·2022년 1월 13일

Union Find 알고리즘

알고리즘

목록 보기

11/45

11. union-find

합집합 찾기, 동일 부모 노드를 보유하고 있는 요소를 찾기 위한 알고리즘으로 서로소 집합(연결관계가 없는 노드)을 탐색하기 위한 알고리즘이기도 하다.

여러개의 노드가 존재할때, 두 노드를 선택해서 서로 같은 graph에 속하는지 판별한다.
Strongly-connected-component 알고리즘(강결합) 등에 적용할 수 있는 기초적인 알고리즘이기도 하다.

11-1. 연결상태의 표현

아래와 같이 연결되어있지않은 상태의 노드들이 분포되어있다고 가정해보자.

이 연결관계가 없는 노드들은 자기자신만을 가르키고, 자신만을 원소로 가지는 형태로 배열표현이 가능하다.

이때 인덱스는 각 노드번호를 의미하고, value값은 부모노드의 번호를 의미한다.

여기서 1과 2 노드를 연결했을때, 보통 작은 숫자를 부모노드로 설정한다.
이때 노드2의 부모노드는 1이 되고 이 과정을 "합친다(union)"라 하고, 연결된 상태는 아래와 같이 다시 배열로 작성해줄 수 있다.

11-2. union find의 의미

다시 동일한 과정으로 1,2,3을 연결하였을때의 graph 상태와 배열은 아래와 같이 나타낼 수 있다.

이때 1,3은 동일한 graph에 속하는 노드들이기 때문에, 서로 연결되어있다고 말할 수 있다.
이러한 연결관계를 어떻게 파악할 수 있는가가 union find의 핵심이고, 이는 동일한 부모노드를 가지고 있는지 파악하는 전체적인 과정을 구현할 수 있는지가 중요하다.

3과 1이 동일한 graph에 있는지(동일한 부모노드인지) 확인하는 과정은 아래와 같다.

3의 부모를 찾기위해 3노드가 가르키는 2노드를 탐색
2노드의 부모노드인 1노드를 탐색, 1노드가 자기 자신을 가르키는 부모노드임을 확인
최종적으로 3노드의 부모노드는 1노드가 되고, 서로 연결되어있는 상태로 간주 가능

11-3. 알고리즘 구현

부모노드를 찾는 과정, 부모노드를 설정해서 서로 연결하는 과정을 구현하고 union find 과정을 최종 구현한다.

array = [0, 1, 2, 3, 4, 5, 6, 7, 8]


# 부모노드 찾기(1차구성)
def getParent(array, value):
    if array[value] == value:
        return array[value]
    return getParent(array, array[value])


# 부모노드 합치기(2차구성)
def unionParent(array, value1, value2):
    value1 = getParent(array, value1)
    value2 = getParent(array, value2)
    if value1 < value2:
        array[value2] = value1
    else:
        array[value1] = value2


# 같은 부모를 가지는지(같은 graph의 node인지) 확인하기
def findParent(array, value1, value2):
    value1 = getParent(array, value1)
    value2 = getParent(array, value2)
    if value1 == value2:
        return True
    else:
        return False


unionParent(array, 1, 2)
unionParent(array, 2, 3)
unionParent(array, 3, 4)
unionParent(array, 5, 6)
unionParent(array, 6, 7)
unionParent(array, 7, 8)
print(array)

print(findParent(array, 1, 2))
print(findParent(array, 4, 5))