서로소 집합 (with JavaScript)

# 서로소 집합 (Disjoint sets)

서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.

아래 그림의 왼쪽 두 집합은 서로소 관계이며, 오른쪽은 아니다.

서로소 집합은 여러 개의 서로소 관계로 이루어진 데이터를 처리하기 위한 자료구조로 사용되며 몇몇 그래프 알고리즘에서 주요하게 사용된다.

 

서로소 집합은 union / find 두 가지 연산으로 구현할 수 있으며, 이 때문에 union-find 자료구조로 불리기도 한다.

Union 연산은 2개의 집합을 하나로 묶는 연산이며, find 연산은 특정 원소가 어느 집합에 속해있는지 찾는 연산이다.

서로소 관계인지 확인 시에는 find 연산의 결과가 다른지 확인하면 된다.

 

# Process

• 모든 연결 관계에 대하여 union 연산을 이용해 서로 연결된 노드들을 합친다.
  • 연결된 노드는 index가 작은 원소가 큰 원소의 부모가 되도록 하여 표현한다.
• 원하는 원소에 대해 find 연산을 진행한다.
  • find 연산의 결과는 가장 상위 부모를 반환한다.

Ex. 

집합 {1, 2, 3, 4, 5, 6}에 대하여 다음 연산을 수행했을 때 서로소 집합 관계를 구해보자.

  1. union(1, 4)

  2. union(2, 3)

  3. union(2, 4)

  4. unoin(5, 6)

연산 결과 아래와 같은 집합이 형성됨을 알 수 있다.

원소 '3'과 원소 '6'이 서로소 관계임을 확인하자.

  find(3) = 1

  find(6) = 5

두 연산의 결과가 다르므로 '3'과 '6'은 서로소 관계임을 알 수 있다.

 

# 구현

일반적인 구현

union과 find를 구현하자.

구현 시 부모 노드를 저장하기 위해 배열을 생성하고 자기 자신을 부모로 하도록 초기화하였다. (0번 노드는 무시한다.)

function find(parent, x) {
  // 재귀적으로 root 탐색
  if (parent[x] !== x) {
    return find(parent, parent[x]);
  }
  return x;
}

function union(parent, a, b) {
  a = find(parent, a);
  b = find(parent, b);

  // 작은 원소를 부모로 설정
  if (a < b) {
    parent[b] = a;
  } else {
    parent[a] = b;
  }
}

const input = [1, 2, 3, 4, 5, 6];
// 자기 자신을 부모로 삼도록 초기화
const parent = new Array(input.length + 1).fill().map((_val, idx) => idx);

// 연산 실행
union(parent, 1, 4);
union(parent, 2, 3);
union(parent, 2, 4);
union(parent, 5, 6);

console.log(parent);
// Result: [0, 1, 1, 2, 1, 5, 5]

console.log(find(parent, 3));
// Result:  1

console.log(find(parent, 6));
// Result:  5

 

경로 압축 구현

여기서 보통은 find 함수를 개선하는 작업을 추가로 진행한다.

일반적인 구현 방식을 따랐을 때 아래 집합에서 'find(parent, n)'을 실행한다고 하면, 시간 복잡도는 O(n)이다.

여기에 union 연산이 m번 있다고 하면 시간 복잡도는 O(n * m)이 되므로 비효율적이다.

 

이는 같은 집합 내의 모든 노드의 부모를 root 노드로 통일하여 해결할 수 있다.

이 경우 find의 시간 복잡도는 O(α(N))라고 한다.

α(x)는 *역 아커만 함수이며, x가 2의 65536제곱일 때 함수 값이 5가 된다고 한다.

따라서, 왠만한 경우에는 시간 복잡도를 O(1)로 간주할 수 있다.

 

구현은 find 함수 실행 시 input parameter의 부모를 재설정해주도록 하면 된다.

function find(parent, x) {
  if (parent[x] !== x) {
    parent[x] = find(parent, parent[x]);
  }
  return parent[x];
}

 

다만, 이럴 경우 parent array 상에서 부모가 root가 아닌 노드가 존재할 수 있다.

맨 처음 예제에서처럼 'union(1, 4), union(2, 3), union(2, 4), union(5, 6)'을 실행하면 다음과 같은 연결 관계를 가지게 된다.

union(2, 4)가 union(2, 1)로 치환되어 실행되지만, '2'의 child인 '3'에 대한 처리는 없기 때문에 '3'의 부모는 '2'로 남아있는 것이다.

따라서 부모를 찾을 때 parent array에서 값을 직접 가져오면 안되고 항상 find 함수를 이용해 찾아와야 한다.

(+ 이름은 find인데 내부적으로 parent array 값을 바꾸게 되는 점 또한 코딩 컨벤션 관점으로 마음에 들지 않긴 한다.)

 

---

역 아커만 함수

경로 압축 시간 복잡도를 검색해보면 대부분의 블로그 글에서 아커만 함수라고 설명하고 있으나, 구글링해보면 역 아커만 함수가 맞는 것 같다.

아커만 함수는 input이 매우 작아도 결과값이 매우 커지게 되며, 오히려 그 역함수에 대한 설명에서 서로소 집합 자료 구조에 대한 언급과 최대값이 5보다 작다는 것을 볼 수 있다.

https://ko.wikipedia.org/wiki/%EC%95%84%EC%BB%A4%EB%A7%8C_%ED%95%A8%EC%88%98#%EC%97%AD%ED%95%A8%EC%88%98