[Algorithm] Union-Find 알고리즘

Union-Find는 대표적인 그래프 알고리즘이며, 서로소 집합(Disjoint-Set) 알고리즘이라고도 불린다. 합집합 찾기라는 의미입니다. 여러개의 노드가 존재할 때 두 개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다. 

 

1. 자기 자신만을 집합의 원소로 가지고 있다고 생각하면 아래 표와 같다.

부모노드	1	2	3	4	5	6	7	8
자식노드	1	2	3	4	5	6	7	8

2. 1, 2와 3이 연결되어있다고 생각하면, 작은값을 부모 노드로 올리는게 일반적이다.이것을 합침(Union)이라고 한다.

하지만, 1,2,3이 같은 집합내에 있지만, 3의 부모노드가 다르다는걸 알 수 있다.  이를 확인하기 위해서 재귀함수를 사용하고, Union-Find라고 한다. 

부모노드	1	1	2	4	5	6	7	8
자식노드	1	2	3	4	5	6	7	8

 

 

함수 구현

## 부모 노드를 찾는 함수
def getParent(parent, x :int):
    if parent[x] == x: return x
    return getParent(parent, parent[x])

## 두 부모 노드를 합치는 함수
def unionParent(parent, a, b):
    a= getParent(parent, a)
    b= getParent(parent, b)
    if a < b: parent[b] = a
    else: parent[a] = b

## 부모가 같은지 확인하는 함수
def findParent(parent, a, b):
    a = getParent(parent, a)
    b = getParent(parent, b)
    if a == b: return 1
    else: return 0
 
## 위 함수 구현 확인 예제
parent=list(range(5))
unionParent(parent, 1, 2)
unionParent(parent, 2, 3)

if findParent(parent, 2,4):
    print('같은 부모입니다.')
else:
    print('다른 부모입니다.')

 

 

 

 

 

 

 

 

 

# 참고 자료