유니온 파인드(Union-Find)

그래프 알고리즘 문제를 풀다 보면 "A 노드와 B 노드가 현재 같은 그룹에 속해 있는가?" 혹은 "두 그룹을 하나의 그룹으로 합쳐라" 같은 요구사항을 자주 만나게 된다.

이럴 때 배열을 순회하며 일일이 그룹을 확인하면 긴 시간이 소요된다. 이때 사용할 수 있는 것이 바로 서로소 집합(Disjoint Set), 일명 유니온 파인드(Union-Find) 알고리즘이다.

유니온 파인드는 최소 신장 트리(MST) 구현에 절때 빠질 수 없는 중요한 알고리즘이다.

1. 유니온 파인드의 2가지 핵심 연산

이름 그대로 딱 두 가지 기능만 수행합니다.

Find (찾기): 특정 노드가 속한 그룹의 '최상위 부모(Root)'를 찾는다. 부모가 같다면 두 노드는 같은 그룹이다.
Union (합치기): 서로 다른 두 개의 그룹을 하나의 그룹으로 합친다. 한쪽 트리의 루트를 다른 쪽 트리의 루트 자손으로 붙인다.

2. 트리가 합쳐지는 과정

처음에는 모든 노드가 자신을 부모로 가리키는 상태다.

만약 union(1, 2)와 union(3, 4)를 실행하면 1번 노드 밑에 2번 노드가 붙고, 3번 노드 밑에 4번 노드가 붙는다.

이후 union(2, 4)를 실행하면, 2번의 부모인 1번에 4번의 부모인 3번을 찾고 3번 트리를 통째로 1번 트리 밑에 붙인다.

3. 경로 압축 (Path Compression)

유니온 파인드를 단순하게 구현하면, 트리가 한쪽으로만 길게 늘어지는 편향 트리(Linked List) 가 될 수 있다. 이렇게 되면 Find 연산을 할 때마다 최악의 경우 모든 노드를 다 거쳐야 해서 매우 비효율적이다.

이를 해결하는 것이 바로 경로 압축이다. Find 함수를 실행할 때, 만나는 모든 노드의 부모를 최상위 루트 노드로 변경해주는 기법이다.

5번 노드는 원래 3번 노드를 부모로 가리키고 있었지만 find(5)를 실행할 때 가리키는 부모를 최상위 부모인 1번 노드로 갱신하며 경로를 압축한다.

코드 구현

java

static int parents[]

static int find(int a) {
  if(parents[a] == a) return a;
  // return find(parents[a])로 사용할 경우 경로 압축하지 않는 find 함수
  return parents[a] = find(parents[a]);
}

static void union(int a, int b) {
  int rootA = find(a);
  int rootB = find(b);

  if(rootA == rootB) return;  

  parents[rootB] = rootA;
}

parents를 초기화할 때 모든 노드가 자신을 가리키도록 parents[i] = i 로 초기화 해야 한다.

neruu00