[알고리즘] 유니온 파인드(Union-Find) (Swift)

유니온 파인드

• 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘
• 서로소 집합, Disjoint-Set 알고리즘이라고도 불림
• 부모노드를 찾는 Find 연산, 노드를 합치는 Union 연산으로 이루어져있음

위의 이미지에서 1과 6이 같은 그래프에 속하는지 판별할 수 있는 알고리즘 입니다.

Find 연산

부모노드를 찾는 Find 연산을 구현하려 합니다.
parent 라는 이름을 지어준 Int 배열을 사용할 것이고, parent[1] = 3 의 의미는 1번 노드의 부모는 3이다. 라고 정의할 수 있습니다.
먼저, 아무 노드도 연결되어 있지 않다고 가정한다면 현재 노드의 부모노드는 자기 자신일 것입니다.

0번 인덱스는 사용하지 않고, 단순히 번호를 맞춰주기 위해서 0번 인덱스부터 시작하였습니다.

이 그림과 같이 그래프를 연결시켜보겠습니다.

다음과 같은 상태일 것입니다.

i	1	2	3	4	5	6
parent	1	1	2	3	5	5

find 연산은 어떻게 구할 수 있을까요?
4에 대해서 부모노드를 찾으려면 3의 부모노드를 확인하고, 3의 부모가 2니깐 2의 부모 확인.. 1의 부모는 1이므로 4의 부모노드는 1이 됩니다.
재귀 함수를 통해 구현할 수 있습니다.

그런데, 문제가 하나 있습니다.
부모를 찾는 연산이 $O(n)$ 이므로, 트리가 아주 깊은 경우에 계속해서 부모를 찾는 것은 비효율적입니다.
4의 부모를 찾은 후에 parent 배열을 한번 확인해보겠습니다.

아까와 똑같은 상태입니다.
부모 노드를 찾았다면 3, 4의 parent 배열도 1로 바꾸어 주는 작업이 필요하지 않을까요?
1로 바뀌기 전에는 4 -> 3 -> 2 -> 1 로 찾아주어야 하지만 3, 4의 부모노드를 1로 바꿨다면 4 -> 1 로 종료가 될 것입니다.
다음과 같이 작성할 수 있습니다.

다음과 같이 그래프가 변경되었겠군요!

i	1	2	3	4	5	6
parent	1	1	1	1	5	5

Union 연산

이제 노드를 합치는 합집합 연산을 구현해보겠습니다.
아주 단순합니다.
합치려는 A 노드와 B 노드의 부모노드를 찾고, 둘 중 한 부모 노드를 자식 노드로 넣어주면 됩니다.

다음과 같이 구현하면 되겠죠?

4번 노드와 6번 노드를 합쳐보겠습니다.

4번 노드의 부모가 1번 노드 이므로 1번 노드가 5번 노드의 자식으로 들어가게 되었네요.
그래프도 다음과 같이 변경되겠네요.

또 find 연산을 한다면 그래프가 5번을 기준으로 둘러 싸인 모양으로 변경될 것이라고 예상되네요.

전체 코드