union find 알고리즘

그래프에서 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하기 위한 알고리즘입니다. union함수를 통해 집합을 합치고, find함수를 통해 노드가 속한 집합을 찾습니다. 이러한 과정을 거쳐 Disjoint Set자료구조를 구현할 수 있습니다. kruskal 알고리즘을 구현할 때 cycle 발생 여부를 확인하기 위해 사용하기도 하는 등 주로 kruskal 알고리즘과 함께 사용됩니다.

Disjoint Set

disjoint는 공통으로 포함하는 원소가 없는 두 집합의 관계를 의미합니다. 그에 따라, disjoint set은 서로 공통 원소가 없는 집합을 의미합니다. 예를 들어, 어떤 집합 S = {1, 2, 3, 4}일 때, A = {1, 2}, B = {3, 4}를 가진 상태라면 A와 B 집합은 disjoint set이라고 할 수 있습니다. 이처럼 disjoint set이 되는 노드끼리 연결되는 경우, 각자의 네트워크(그래프)를 갖게 됩니다. A와 B는 서로 연결되어 있지 않습니다.

알고리즘의 과정

Union find 알고리즘은 초기화(makeSet) - 합치기(union) - 찾기(find) 연산 과정을 거칩니다. 초기화 연산은 각각의 노드로 집합을 만드는 과정입니다. 노드가 10개라면 집합 또한 10개이고, 각 노드는 그 집합에 유일한 노드가 됩니다. 합치기(union) 연산을 통해 집합끼리 합칠 수 있고, 찾기(find) 연산을 통해 어떤 노드가 속한 집합의 루트 노드를 찾을 수 있습니다.

makeSet, union, find

makeSet(x) : x를 유일한 원소로 하는 새로운 집합을 생성
union(x,y) : x가 속한 집합과 y가 속한 집합을 합친다.
find(x) : x가 어떤 집합에 속해있는지 찾는다.

makeSet함수는 union, find연산을 하기 전, 각 노드를 하나의 집합으로 초기화하는 과정입니다. 예를 들어, 0부터 10까지 노드가 있을 때, {0}, {1}, {2}, …, {10}처럼 하나의 유일한 노드를 가지는 집합으로 만듭니다. union함수는 두 집합을 합치는 과정입니다. 0, 1을 합치면 {0, 1}, {2}, …, {10}처럼 집합이 합해져 하나의 집합이 됩니다. find함수는 주어진 노드가 속한 집합의 대표 노드를 반환합니다. 같은 집합에 속한 노드는 대표 노드가 항상 같으므로, 두 노드가 같은 집합에 속해있는지 확인할 수 있습니다.

집합을 구현할 자료구조

union find 알고리즘에서 집합을 구현하기 위해선 트리 구조가 가장 효율적인 자료구조로서 사용됩니다. 트리 구조에서는 루트 노드가 존재하므로 대표 원소로 설정하기 용이합니다. 이렇게 자식 노드가 대표 노드를 알아야 하기 때문에 보통의 트리에서는 부모 노드가 자식 노드를 가리키지만, 집합을 표현하는 트리 구조에서는 자식 노드가 부모 노드를 참조하고 있어야 합니다.

union find 알고리즘이 비효율적일 때

Union find 알고리즘을 구현하기 위해선 트리 구조가 효율적이라고 했지만, 트리 구조는 최악의 경우 연결 리스트 형태가 되어버릴 수 있습니다. 이러한 경우, 시간 복잡도가 O(n)이 되므로 트리 구조로서의 장점이 사라지므로 최적화 과정이 필요하게 됩니다. 이를 해결하기 위해 경로 압축이나 union by rank 방법을 적용해야 합니다.

경로 압축과 union by rank

두 최적화 방법 모두 find 연산에서 더 효율적인 시간복잡도를 얻어내기 위해 사용합니다. union by rank방법의 경우, 노드마다 rank라는 변수를 하나 선언해서 트리로부터 노드의 높이를 값으로 할당합니다. rank를 통해 트리의 높이가 상대적으로 낮은 트리를, 높이가 높은 트리에 합해서 트리가 더욱 깊어지지 않도록 하는 방법입니다. 경로 압축의 경우, 간단하게 모든 노드의 부모 노드를 대표 노드로 변경하는 것입니다. find가 결국 대표 노드를 찾는 것이므로 매우 효율적인 방법이라고 할 수 있습니다.

// 그래프의 노드의 개수가 n개 일 때
// 자기 자신이 부모 노드로 존재하는 배열 생성
const parent = [];
for(let i = 0 ; i <= n ; i++) parent[i] = i;

// x가 어떤 집합에 속해있는지 재귀 함수를 이용해서 찾는다.
const getParent = (parent, x) => {
  if(parent[x] === x) return x;
  return parent[x] = getParent(parent, parent[x]);
}

// x와 y가 속한 집합(parent)을 찾아
// 둘중 더 작은 부모 값으로 합친다.
const union = (parent, x, y) => {
  const s1 = getParent(parent, x);
  const s2 = getParent(parent, y);
  if(s1 < s2) return parent[s2] = s1;
  else return parent[s1] = s2;
}

// x와 y가 속한 집합(parent)이 같은 부모를 갖는지 확인한다.
const find = (parent, x, y) => {
  const s1 = getParent(parent, x);
  const s2 = getParent(parent, y);
  if(s1 === s2) return true;
  else return false;
}