합집합 찾기, 동일 부모 노드를 보유하고 있는 요소를 찾기 위한 알고리즘으로 서로소 집합(연결관계가 없는 노드)을 탐색하기 위한 알고리즘이기도 하다.
여러개의 노드가 존재할때, 두 노드를 선택해서 서로 같은 graph에 속하는지 판별한다.
Strongly-connected-component 알고리즘(강결합) 등에 적용할 수 있는 기초적인 알고리즘이기도 하다.
아래와 같이 연결되어있지않은 상태의 노드들이 분포되어있다고 가정해보자.
이 연결관계가 없는 노드들은 자기자신만을 가르키고, 자신만을 원소로 가지는 형태로 배열표현이 가능하다.
이때 인덱스는 각 노드번호를 의미하고, value값은 부모노드의 번호를 의미한다.
여기서 1과 2 노드를 연결했을때, 보통 작은 숫자를 부모노드로 설정한다.
이때 노드2의 부모노드는 1이 되고 이 과정을 "합친다(union)"라 하고, 연결된 상태는 아래와 같이 다시 배열로 작성해줄 수 있다.
다시 동일한 과정으로 1,2,3을 연결하였을때의 graph 상태와 배열은 아래와 같이 나타낼 수 있다.
이때 1,3은 동일한 graph에 속하는 노드들이기 때문에, 서로 연결되어있다고 말할 수 있다.
이러한 연결관계를 어떻게 파악할 수 있는가가 union find의 핵심이고, 이는 동일한 부모노드를 가지고 있는지 파악하는 전체적인 과정을 구현할 수 있는지가 중요하다.
3과 1이 동일한 graph에 있는지(동일한 부모노드인지) 확인하는 과정은 아래와 같다.
부모노드를 찾는 과정, 부모노드를 설정해서 서로 연결하는 과정을 구현하고 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))
array = [0, 1, 2, 3, 4, 5, 6, 7, 8]
와 같이 array가 비어있지않은 상태에서 값을 대입하거나 삽입할 수 있다.
빈 배열에 인덱싱을 하거나 값을 대입, 접근할때는 index error가 발생함을 유의한다.
index error
https://power-of-optimism.tistory.com/123