[알고리즘] 유니온 파인드

집합이 있을 때 어떤 원소가 어떤 부분집합에 속하는지 알아내는 알고리즘이 파인드, 두개의 부분집합끼리 합집합을 해주는 알고리즘이 유니온 (union)이다. 대표적으로 다음 글에 다룰 크루스칼 알고리즘에서 사용된다: [알고리즘] 크루스칼 알고리즘 (+LeetCode 1584). 사실 트리, 집합 등 다양한 상황에서 사용할 수 있는데, 여기서는 트리 구조에서 설명해보겠다 (다른 상황에도 별로 다르지 않다). 그림으로 보면 이해하기 쉬울 것이다:

여기서 같은 색으로 칠해진 원소들은 같은 부분집합이다. 그리고 같은 부분집합의 원소들은 (연결된) 트리를 이루고 있다.  가장 위에 그림에서는 원소 1이 빨강 부분집합에만 해당되지만 1과 2를 연결한다면 검정에도 속하게 된다. 이 때 1이 빨강 부분집합에 해당하는 것을 찾는 알고리즘이 파인드다. 그리고 빨강과 검정이 연결되어있기 때문에 두 부분집합을 합해서 모두 빨강 부분집합으로 만드는 것이 유니온이다.

 

그럼 이 문제를 어떻게 푸는게 효율적일까? 우선 파인드 알고리즘부터 살펴보자. 1번 원소가 빨강, 파랑, 검정에 속할 수 있기 때문에 가장 무식한 방법은 이것을 모두 확인하는 것이다. 하지만 더 효율적으로 진행할 수 있다. 우선 각 부분집합마다 root node를 정하는 것이다. 예를 들어서 빨강같은 경우 0, 검정같은 경우 2, 파랑같은 경우 4를 root node로 잡을 수 있다 (어떤 node를 root로 잡는지는 크게 중요하지 않다). 그리고 각 node마다 parent node를 정한다. 예를 들어 1번의 parent node를 3번, 3번의 parent node를 0번으로 잡을 수 있다. 이제 1번의 root node가 0, 4, 2인지 확인해서 빨강, 파랑, 검정 집합에 해당되는지 확인할 수 있다. 이 때 root node를 찾기 위해서 node의 parent들을 거슬러 올라가면 되는데, 더 효율적으로 각 node의 root node를 저장해두면 이것도 필요가 없게 된다. 

 

위에 설명한 예를 다음과 같이 구현할 수 있다:

N=6 # 원소의 수

# 우선 모든 node의 parent를 자신으로 잡는다 (연결 구조가 없는 상태)
def init_parents(N):
	return [i for i in range(N)]
parents = init_parents(N)

# root를 찾는 코드
def find(i):
	# parent가 자신이면 리턴
	if parents[i]==i:
		return i
    # 자신의 parent를 재귀적으로 구한다.
    # 효율을 위해서 이 결과값을 parents에 저장한다 (parent node 대신 root node 저장)
	parents[i]=find(parents[i])
	return parents[i]

# 두 부분집합의 union을 해주는 코드
def union(a,b):
	# 우선 root부터 구한다
	a = find(a)
	b = find(b)
    # 편의상 더 낮은 root index를 합집합의 root index로 설정한다
	if a<b:
		parents[b] = a
	else:
		parents[a] = b
        
# 예시 구현
print(parents, "node 초기화")
union(0,3)
print(parents, "0,3 union")
union(1,3)
print(parents, "1,3 union")
union(4,5)
print(parents, "4,5 union")
union(1,2)
print(parents, "1,2 union")

출력 값:

reference: https://en.wikipedia.org/wiki/Disjoint-set_data_structure