Union-Find JS 구현

Union-Find(합집합 찾기)

Union-Find(유니온-파인드)는 대표적인 그래프 알고리즘이며 서로소 집합(Disjoin-Set) 알고리즘이라고도 부른다. 위 그림과 같은 그래프가 존재할 때, 두 개의 노드를 선택해서 해당 노드들이 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

처음 8개의 노드가 무분별하게 존재한다고 가정한다. 모두 연결되지 않고 각각 자기 자신만을 요소로 갖고 있을 때 아래 표와 같이 표현할 수 있다.

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	2	3	4	5	6	7	8

1번 노드와 2번 노드가 연결되면 2번 노드의 부모 노드 번호(인덱스)에는 "1"이 할당되고 아래 표처럼 표현할 수 있다.

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	1	3	4	5	6	7	8

부모 노드를 합칠 때는 일반적으로 더 작은 값으로 합치고 이것을 Union이라고 부른다.

2번 노드와 3번 노드가 연결되면 마찬가지로 3번 노드의 부모 노드 번호(인덱스)에는 "2"가 할당되고 아래 표처럼 표현할 수 있다.

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	1	2	4	5	6	7	8

하지만 1번 노드와 3번 노드가 연결되었는지 확인 작업이 필요하다. 3번 노드의 현재 부모 노드로 할당된 2번 노드를 찾고, 그 다음 2번 노드의 부모 노드인 1번 노드를 찾아 3번 노드는 1번 노드까지 연결되어있다는 사실을 파악할 수 있다. 이는 재귀 함수를 통해 확인할 수 있다.

위 과정을 반복해서 수행하면 아래 표와 같이 구성되고 3개의 그래프로 나타낼 수 있다.

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	1	1	4	4	4	7	7

---

구현

function main(n) {
  /*
  인덱스는 노드 번호를 뜻하고 요소는 부모 노드를 의미
  최초 배열은 자기 자신이 부모 노드
  예) 입력 n = 3 -> [empty, 1, 2, 3] 배열 생성
                    노드 1의 부모 노드: 1,
                    노드 2의 부모 노드: 2,
                    노드 3의 부모 노드: 3
  */
  const arr = new Array(n);

  for (let i = 1; i <= n; i++) {
    arr[i] = i;
  }
  
  // 간선 연결
  unionParent(arr, 1, 2);
  unionParent(arr, 2, 3);
  unionParent(arr, 4, 6);
  unionParent(arr, 6, 5);
  unionParent(arr, 7, 8);

  console.log(arr); // [1, 1, 1, 4, 4, 4, 7, 7]

  console.log(findeParent(arr, 1, 2)); // true
  console.log(findeParent(arr, 1, 3)); // true
  console.log(findeParent(arr, 3, 5)); // false
  console.log(findeParent(arr, 4, 5)); // true
  console.log(findeParent(arr, 6, 8)); // false
}

// 최상위 부모 노드를 찾는 재귀 함수
function getParent(arr, n) {
  if (arr[n] === n) return n;

  return (arr[n] = getParent(arr, arr[n]));
}

// 두 개의 노드를 같은 부모 노드로 병합하는 함수
function unionParent(arr, a, b) {
  a = getParent(arr, a);
  b = getParent(arr, b);

  // 두 노드 중 부모 노드 값이 더 작은 값으로 합친다
  if (a < b) arr[b] = a;
  else arr[a] = b;
}

// 2개의 노드가 같은 부모 노드를 가졌는지 확인하는 함수
function findeParent(arr, a, b) {
  a = getParent(arr, a);
  b = getParent(arr, b);

  if (a === b) return true;
  else return false;
}

main(8);

---

참고
17. Union-Find(합집합 찾기)_안경잡이개발자님 블로그