yeolyi.com성열의 컴퓨터공학

유니온 파인드

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

컴퓨터 여덟 대를 케이블로 하나씩 잇는다고 합시다. 케이블을 이을 때마다 1번과 7번 컴퓨터 사이에 데이터가 오갈 수 있는지 묻고 싶습니다. 케이블로 이어진 컴퓨터들을 한 무리로 보면, 할 일은 두 무리를 합치기(union)와 두 컴퓨터가 같은 무리인지 찾기(find) 둘입니다.

무리 번호

컴퓨터마다 무리 번호를 배열에 적어 두면 찾기는 번호 두 개만 비교하면 됩니다. 하지만 합칠 때는 한쪽 무리의 컴퓨터를 모두 찾아 번호를 고쳐야 합니다. 배열 전체를 훑으니 컴퓨터가 n대면 O(n)입니다.

대표를 가리키는 트리

번호 대신 컴퓨터마다 부모 하나만 적어 둡시다. 그러면 무리마다 트리가 하나 생기고, 루트가 그 무리의 대표입니다. 지금까지의 트리와 달리 자식이 부모를 가리키고, 루트는 자기 자신을 부모로 적습니다.

이렇게 원소들을 무리로 나눠 두고 합치기와 찾기를 하는 자료구조를 유니온 파인드(union-find)라 합니다.

a
b

원소 두 개를 골라 합치거나 찾아봅시다.

12345678
부모 배열 (아래 수가 칸 번호)
1122334455667788

하이라이트된 노드가 대표, 굵은 테두리가 찾으며 지나온 노드입니다. 이 데모는 a의 대표를 b의 대표 아래에 답니다.

  1. 1과 2, 3과 4를 합쳐 봅시다.
  2. 2와 4를 합친 뒤 1과 3을 찾아봅시다.

같은 순서를 C로 옮기면 다음과 같습니다.

1#include <stdio.h>
2
3// 컴퓨터 1~8의 부모. 처음엔 모두 자기 자신이
4// 대표(0번 칸은 쓰지 않는다)
5int parent[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
6
7int find(int x) {
8 while (parent[x] != x) {
9 x = parent[x];
10 }
11 return x;
12}
13
14// 합치기(union은 C가 이미 쓰는 낱말)
15void unite(int a, int b) {
16 parent[find(a)] = find(b);
17}
18
19int main(void) {
20 unite(1, 2);
21 unite(3, 4);
22 unite(2, 4);
23 printf("%d %d\n", find(1), find(3));
24 return 0;
25}

변수 없음
출력 없음

재생하며 parent에서 바뀌는 칸을 봅시다.

크기 합치기와 경로 압축

합치는 순서가 나쁘면 트리가 한 줄로 늘어서 찾기가 O(n)이 됩니다. 두 가지 방법으로 막습니다.

a
b

원소 두 개를 골라 합치거나 찾아봅시다.

12345678
부모 배열 (아래 수가 칸 번호)
2132435455667788
  1. 1과 5를 찾아봅시다.
  2. 6과 7을 합친 뒤 1과 7을 합쳐 봅시다.
  3. 처음으로 돌아가 크기 합치기와 경로 압축을 끄고 같은 순서로 해 봅시다.

둘을 함께 쓰면 연산을 여러 번 할 때 한 번에 걸리는 시간이 평균적으로 거의 상수입니다. 1975년 타잔(Robert Tarjan)은 이 시간이 느리게 자라는 함수 α(n)에 비례함을 밝혔습니다. α(n)은 현실에서 다룰 어떤 n에서도 4를 넘지 않습니다.

마무리

이번 파트에서는 값을 갈래로 뻗게 담는 트리를 다뤘습니다. 트리는 위아래 관계를 담고, 이진 탐색 트리와 AVL 트리는 순서를 지키며 층 수만큼만 비교해 찾고 넣습니다. 힙은 가장 작은 값을 늘 루트에 두고, 유니온 파인드는 무리를 합치고 찾는 일을 거의 상수 시간에 합니다. 그런데 이진 탐색처럼 정렬된 데이터를 쓰려면 먼저 정렬해야 하고, 알고리즘 글의 선택 정렬은 O(n²)입니다. 정해진 풀이 없이 경우를 하나씩 만들어 봐야 하는 문제도 있습니다. 그래서 다음 파트에서는 문제를 다 해 보거나 작게 쪼개서 푸는 방법을 다룹니다. 첫 글은 재귀입니다.

도전 문제

원소 1000개가 처음에 모두 따로 있습니다. 경로 압축 없이 크기 합치기만 쓰며 합치기를 원하는 만큼 합니다. 크기가 같은 두 트리를 합칠 때는 어느 쪽을 아래에 달아도 됩니다. 그 뒤 찾기 한 번에 부모를 따라 올라가는 횟수는 가장 많을 때 몇 번일까요? 숫자로 답하세요.