Union-Find Structure

Disjoint Set

  Union-Find Sturucture이란 서로소 집합(Disjoint Set)을 저장하기 위한 자료구조이다. 서로소 집합이란 그림과 같이 공통원소가 존재하지 않는 두 집합을 의미한다. Union-Find는 두 노드가 서로 같은 그래프에 속하는지 판별하거나 그래프의 사이클(순환 경로)을 판별하기 위해 사용한다. 

 

1. Operation

Find: 특정 원소가 속한 부분 집합을 구한다.
Union: 2개의 부분 집합을 하나의 부분 집합으로 합친다.

  Union-Find 구조는 Find와 Union 2가지 연산으로 구성된다. Find는 자료구조 내에서 해당 원소가 속해있는 집합을 찾는 연산이다. Union은 두 개의 집합을 합칠 수 있는 경우 합치는 연산이다.

 

2. Example

Graph

  위와 같은 노드와 경로가 있다고 생각해보자. 위 그래프는 3개의 서로소 집합으로 나눌 수 있다. Union-Find 구조는 위와 같은 그래프를 서로소 집합으로 분류하고, 각 원소가 어떤 집합에 속하는지 쉽게 찾아낼 수 있다. Union-Find 구조를 만들어보자

 

Initial Storage

  Union-Find 구조는 노드 갯수만큼의 저장공간을 갖는다. 저장 공간의 인덱스 그래프상의 노드를 의미하며, 값은 해당 노드가 속한 노드의 root 노드를 의미한다. 각 노드의 root 노드 초기 값은 자신의 노드 번호로 한다.

 

SubGraph1

  이 상황에서 [0, 1], [1, 2] 경로들을 Union-Find 구조에 적용시켜보자. 이 때 그래프의 root를 어떤 방식으로 결정할지 정해야하는데 이 글에선 간단하게 노드 번호가 가장 작은 요소가 루트가 되는 규칙을 적용하기로 하자.

 

  먼저 [0, 1] 경로에 대해 우선 각각의 root를 구한다(Find 연산). 아직 아무런 경로도 적용되지 않았기 때문에 결과는 [0, 1] 이다. 그 후에는 두 노드를 합친다. 둘 사이에 경로([0, 1])가 있으므로 합쳐지는지 여부는 따질 필요가 없다. 이 때 가장 작은 요소가 루트가 되는 규칙이 적용된다. 즉, 루트가 더 작은 요소인 0 아래에 1이 들어간다. (이 규칙은 각 노드도 요소가 1개인 집합이라고 생각할 수 있기 때문에 여러 개의 요소를 가진 두 집합 간에도 적용된다. cf. 트리 구조의 부분트리)

 

Storage - SubGraph 1

  경로 [0, 1], [1, 2] 가 적용된 결과는 위와 같다. 1과 2번 노드의 root가 0이된 것을 볼 수 있다. 즉, 0, 1, 2번 노드는 모두 같은 그래프 상에서 연결되어있다는 점을 알아낼 수 있다. 이러한 연산을 반복해나가다보면 다음과 같은 결과를 얻게된다.

 

Storage - Result

  최종 결과를 보면 (0, 1, 2)가 같은 그룹, (3, 4, 5)가 같은 그룹, (6, 7)이 같은 그룹에 속한다는 것을 알 수 있게 되며, 두 노드가 주어졌을 때 두 노드가 서로 연결되어있는지도 확인 가능하다.(같은 그룹에 속하는지 확인한다)

 

3. Code

function solution(n, paths) {
  const roots = [...Array(n)].map((_, i) => i);

  const find = (n) => {
    if (roots[n] === n) return n; // root는 값이 자기 자신이다.
    else return find(roots[n]); // root를 찾아나간다. roots[n] = find(roots[n]) 최적화 가능
  }

  const union = (x, y) => {
    let rootX = find(x);
    let rootY = find(y);

    if (rootX === rootY) return false;
    if (rootX < rootY) roots[rootY] = rootX; // 항상 작은 값을 루트로 설정
    else roots[rootX] = rootY;
  }

  // 경로 적용하기
  for (const path of paths) {
    const [start, end] = path;
    union(start, end);
  }
  return roots; // [0, 0, 0, 3, 3, 3, 6, 6]
}

console.log(solution(8, [[0, 1],[1, 2],[3, 4],[3, 5],[7, 6]]));

  find는 root를 찾는 연산으로, 어떤 요소가 root라면 해당 요소의 값은 자기 자신임을 이용하여 구현한다. 만약 Union-Find 구조에서의 값이 자기 자신이 아니라면 해당 요소는 root가 아닌 것이고, 자신의 root를 찾기 위해 재귀호출로 root를 최대한 찾는다. 이 때 find를 수행하며 만나는 모든 값의 부모 노드를 갱신(roots[n] = find(roots[n]) 하여 경로를 압축하는 최적화도 가능하다.(https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html)

 

  union은 각 경로를 적용하면서 그래프들(노드 1개로 이루어진 그래프)을 하나로 합치는 연산이다. root가 이미 동일하면 합치지 않고, 다르다면 더 작은 값을 둘의 루트로 삼는다.