분리 집합과 유니온 파인드
유니온 파인드는 어떤 원소가 포함된 집합을 찾거나 어떤 두 정점이 그래프 상에서 연결되어있는지 확인하는데 사용할 수 있는 알고리즘입니다.
양방향 연결 그래프에서 간선으로 서로 연결된 정점들을 하나의 집합으로 볼 수 있으니 사실 두 말을 같은 의미입니다.
요구 사항
유니온 파인드는 세 개의 핵심 요소로 구성됩니다.
- 어떤 정점 $i$의 부모 정점 정보 $P[i]$를 담고 있는 배열 $P$
- 배열 $P$에서 어떤 정점 $i$의 최상위 부모를 찾는 탐색 연산
find - 어떤 두 정점에 대해 한 정점을 다른 정점의 부모로 설정하여 두 정점을 하나의 집합으로 병합하는 병합 연산
merge(union)
부모 배열 $P$의 초깃값은 다음과 같이 선언할 수 있습니다.
1
P = [i for i in range(n)]
0부터 $N-1$까지의 모든 원소에 대해, 그 어떤 정점도 서로 연결되어있지 않다면 모든 정점은 자기 자신이 최상위 부모인 트리라고 생각할 수 있습니다.
다시 말해 모든 원소는 자기 자신만을 원소로 갖는 자신만의 집합을 가지고 있는 셈입니다.
탐색 연산의 정의
부모 배열 $P$는 정점 사이의 연결 관계가 업데이트됨에 따라 계속해서 수정됩니다. 수정 방법은 병합 연산에서 더 살펴보겠지만, 우선 정의에 따라 다음과 같은 $P$가 있다고 가정하겠습니다.
1
P = [1, 2, 3, 4, 5, 5]
$P$에 따르면 정점 0의 부모는 1, 1의 부모는 2, …, 4의 부모는 5이고, 5의 부모는 5 자기 자신입니다.
어떤 정점이든 부모를 계속 거쳐 탐색하면 언젠가 최상위 부모에 도달하게 되므로 다음과 같이 탐색 연산을 재귀적으로 정의할 수 있게 됩니다.
1
2
3
4
def find(n: int) -> int:
if P[n] == n:
return n
return find
탐색 연산 find(n)은 $n$이 최상위 부모라면 재귀적인 탐색을 중단하고 $n$ 자기 자신을 반환합니다. 최상위 부모가 아니라면 부모의 부모를 찾기 위해 find(P(n))을 호출합니다.
병합 연산의 정의
이제 $i$에 대해 부모 정보를 가지고 있는 배열 $P$를 수정하도록 병합 연산을 정의하겠습니다.
다음과 같이, 어떤 두 정점에 대해서 하나의 정점을 다른 하나의 정점의 부모로 지정하겠습니다.
1
2
def merge(a: int, b: int):
P[a] = b
하지만 위와 같은 정의는 상황에 따라서는 탐색 연산 과정에 문제를 일으킬 수 있습니다.
1
2
merge(0, 1)
merge(1, 0)
merge(0, 1)과 merge(1, 0)을 모두 호출한 결과는 P[0], P[1] = 1, 0을 실행한 결과와 같습니다. 즉, 이 경우 0의 부모는 1, 1의 부모는 0으로 지정된 상태입니다.
서로가 서로의 부모인 상태에서 위에서 정의한 탐색 연산을 실행하면 탐색 연산의 종료 조건이 성립하지 않습니다.
탐색 연산은 환경이 허락하는 한 멈추지 않고 재귀적으로 자기 자신을 호출할 것입니다.
주의할 점은 부모 배열 $P$에서 사이클이 생기면 안된다는 것입니다.
따라서 사이클이 발생하지 않도록, “부모를 바라보는 방향이 일관되도록” 조정해야합니다.
1
2
3
def merge(a: int, b: int):
a, b = a, b if a < b else b, a
P[a] = b
사이클을 막는 가장 쉬운 방법은 원소 번호의 대소관계를 이용하는 것입니다.
예를 들어, 무조건 작은 번호를 큰 번호의 부모가 되도록 설정하면 부모를 바라보는 방향은 (작은 번호) <= (큰 번호)가 되므로 일관됩니다.
최적화
유니온 파인드의 기본 골자는 구현해냈지만, 아직 최적화할 여지가 남았습니다.
1
P = [1, 2, 3, 4, 5, ..., 1_000_000_000, 1_000_000_000]
만약 부모 배열 $P$가 위와 같다면 0번 원소의 부모를 찾는데 시간이 꽤 걸릴 것입니다.
따라서 이와 같이 세 단계 이상의 부모를 찾을 때를 위해, 연산 중간에 자신의 부모를 부모의 부모로 갱신해놓을 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
def find(n: int) -> int:
if P[n] == n: return n
P[n] = find(P[n])
return P[n]
def merge(a: int, b: int):
pa, pb = find(a), find(b)
if pa > pb:
P[pa] = pb
P[a] = pb
else:
P[pb] = pa
P[b] = pa
병합 연산의 일관성
유니온 파인드를 활용하는 문제에서 병합 연산을 위와 같이 if-else 구조로 정의한다면 활용하는 방식에 따라 잠재적으로 문제가 발생할 수 있습니다.
merge(a, b)를 병합 연산 용도로만 정의하면 괜찮겠지만, 저는 병합 연산에 문제 해결을 위해 튜닝 코드를 끼워 넣어서 문제를 경험했습니다.
위 코드에서 else가 동작하는 경우의 수는 $Pa < Pb$와 $Pa = Pb$ 두 개입니다.
1
2
3
4
5
6
7
8
9
10
def merge(a: int, b: int):
pa, pb = find(a), find(b)
if pa > pb:
P[pa] = pb
P[a] = pb
(*1)
else:
P[pb] = pa
P[b] = pa
(*2)
(*1)를 $Pa < Pb$일 때 넣을 수 있는 튜닝 코드, (*2)를 $Pb < Pa$일 때 넣을 수 있는 튜닝 코드라면 $Pa = Pb$인 상황에서 예기치 못한 동작이 발생할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
def merge(a: int, b: int):
pa, pb = find(a), find(b)
if pa > pb:
P[pa] = pb
P[a] = pb
(*1)
elif pa < pb:
P[pb] = pa
P[b] = pa
(*2)
따라서 병합 연산에서 최상위 부모의 비교는 if-elseif 구조로 정의하는 것을 권장합니다.
저는 가장 최근에 이 문제에서 최상위 부모의 비교를 if-else로 선언했다가 틀렸습니다.