유니온 파인드

유니온 파인드

유니온 파인드 알고리즘은 같은 전체집합에 속하나, 원소가 겹치지 않는 서로소 집합(Disjoint-set)에서 집합을 합치거나, 같은 집합에 속하는지를 판별하는 것에 효율적인 알고리즘입니다.

유니온 파인드는 집합을 1차원 배열에서 인덱스를 통해 관리합니다. 처음은 모든 원소가 자기 자신을 가리키게 하고, -1로 초기화합니다. 다음은 7번까지의 유니온 파인드 배열입니다.

번호	1	2	3	4	5	6	7
포인터	-1	-1	-1	-1	-1	-1	-1

이때 만약 집합간의 유니온 연산이 일어났다면, 포인터가 가리키는 대상을 바꾸면 됩니다. 예를 들어 3번과 4번을 유니온한다면, 다음과 같이 표현할 수 있습니다.

번호	1	2	3	4	5	6	7
포인터	-1	-1	-1	3	-1	-1	-1

이때 주의해야 할 점은, 포인터를 바꿀 때, 최상위 부모의 포인터를 바꿔야한다는 것입니다. 위의 유니온 파인드 배열에서, 4번과 1번 집합을 유니온한다고 하면, 4번의 포인터를 바꾸는 것이 아닌, 3번의 포인트를 바꿔야합니다.

번호	1	2	3	4	5	6	7
포인터	-1	-1	1	3	-1	-1	-1

경로 압축 휴리스틱

위의 서로소 집합을 그래프로 나타내면 다음과 같습니다.

$\{1, 3, 4\}, \{2\},\{3\},\{6\},\{7\}$입니다. 분명히, 1, 3, 4는 같은 집합에 속해있습니다. 또, 루트는 1로 같습니다. 그런데 4번에서 루트를 찾으려면(파인드), 루트를 찾기 위해 3번으로 간 다음, 3번의 루트인 1번으로 가야합니다. 비효율이 발생합니다. 그렇게 해서 고안된 것이 같은 집합에 있는 노드들의 루트를 그 집합의 최상위 노드 하나로 모두 바꿔버리면 된다는 것이였습니다. 즉, 다음과 같이 표현한다는 것입니다.

번호	1	2	3	4	5	6	7
포인터	-1	-1	1	1	-1	-1	-1

가중치 휴리스틱

위에서는 파인드 연산에서 비효율을 없애기 위해 휴리스틱을 적용하였다면, 이번에는 유니온 연산에서 비효율을 없애기 위해 휴리스틱을 적용합니다. 유니온 연산에서 만약 노드의 수가 많은 집합을 노드의 수가 적은 집합에 붙인다고 해보면, 우리는 집합의 모든 원소의 포인터를 변경해야 하기 때문에, 노드의 수가 적은 집합을 노드의 수가 많은 집합에 붙이는 것이 효율적임을 알 수 있습니다. 이때 가중치 휴리스틱을 적용하는데, 간단히 말해서 루트노드에 그 집합이 가지고 있는 원소의 개수를 표시하도록 만드는 것입니다.

번호	1	2	3	4	5	6	7
포인터	-1	-1	-1	-1	-1	-1	-1

위와 같이 아무런 유니온 연산이 되지 않은 집합에 3번과 4번의 가중치 유니온 연산을 하면, 다음과 같습니다.

번호	1	2	3	4	5	6	7
포인터	-1	-1	-2	3	-1	-1	-1

즉, 가중치 유니온 연산은 -1로 초기화된 배열에서 그 값을 더하여 루트 노드에 저장하고, 포인터는 자신의 노드에 저장하는 방식으로 동작합니다. 이해가 잘 안갈수도 있는데, 일단 5번과 6번을 유니온 해보겠습니다.

번호	1	2	3	4	5	6	7
포인터	-1	-1	-2	3	-2	5	-1

2번과 4번을 유니온하면,

번호	1	2	3	4	5	6	7
포인터	-1	-3	2	2	-2	5	-1

마지막으로 2번과 5번을 유니온하면,

번호	1	2	3	4	5	6	7
포인터	-1	5	5	5	-5	5	-1

다음과 같이 됩니다. 즉, 포인터가 음수일 경우 더 큰 쪽이 노드를 더 적게 가지고 있으므로, 그쪽으로 루트 노드를 정하는 것입니다. 반면에 양수일 경우 그 노드는 루트노드가 아님을 알 수 있습니다.

파이썬 코드

parents = [-1] * n

def find(x):
    if parents[x] < 0:
        return x # 루트 노드 반환
    parents[x] = find(parents[x]) # 경로 압축
    return parents[x]

def union(x, y):
    x_root = find(x)
    y_root = find(y)
    if x_root < y_root:
        parents[x_root] += parents[y_root] # 가중치 더하기 -> 노드의 개수 저장
        parents[y_root] = x_root # 포인터 변경
    else:
        parents[y_root] += parents[x_root]
        parents[x_root] = y_root