[Interview] 알고리즘, 자료구조 - Union find algorithm

Interview는 면접 주제 블로깅으로 자신 있는 주제를 정해서, 이해한 바를 깊고 자세하게 작성한 글이다.

Q. Union find 알고리즘에 대해 아는 만큼 설명해 주세요.

짧은 정답

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

꼬리 질문

Q. Disjoint Set이란?

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

Q. Union find 알고리즘의 과정

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

Q. makeSet 함수, union 함수 그리고 find 함수에 대해서

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

Q. 집합을 구현할 자료구조

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

Q. Union find 알고리즘이 비효율적일 때

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

Q. 경로 압축과 union by rank

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

Union find 알고리즘 구현 (JavaScript)

백준 집합의 표현 문제를 해결하면서 union find 알고리즘에 대해 알아봅시다.

const readline = require("readline");
const reader = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

/**
 * 초기 집합을 반환한다. (배열)
 * 각 집합은 유일한 원소 하나만 갖는 집합이다.
 *
 * 배열의 인덱스는 노드를 의미한다.
 * 배열의 값은 노드가 가리키는 부모 노드를 의미한다.
 * 모든 노드는 각 집합의 루트 노드가 되고, 그러므로 배열의 인덱스와 값은 모두 같다.
 */
function makeSet(n) {
  return Array.from({ length: n + 1 }).map((_, index) => index);
}

/**
 * x가 속한 집합의 부모 노드를 반환한다.
 *
 * 인덱스와 값이 같아지면 루트 노드이다.
 * 배열의 값은 부모 노드를 가리키고 있으므로 이를 따라가면 루트 노드까지 도달할 수 있다.
 */
function find(set, x) {
  if (set[x] === x) return x;
  return set[x];
}

/**
 * x 집합과 y 집합을 합한다.
 *
 * x 집합의 루트 노드를 y 집합의 루트 노드로 바꾸면 된다.
 */
function union(set, x, y) {
  setX = find(set, x);
  setY = find(set, y);
  set[setY] = setX;
}

const lines = [];
reader
  .on("line", (line) => {
    lines.push(line.trim());
  })
  .on("close", () => {
    /**
     * n: 초기 집합의 수는 n + 1
     * m: 입력으로 주어지는 연산의 개수
     */
    const [n, m] = lines.shift().split(" ").map(Number);

    /**
     * init 과정
     */
    const set = makeSet(n);

    /**
     * 0 a b 는 합집합을 의미한다. a가 포함되어 있는 집합과 b가 포함되어 있는 집합을 합한다.
     * 1 a b 는 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산을 한다.
     *
     * 1로 시작(탐색)하는 입력에 대하여 같은 집합에 속하면 YES, 다른 집합에 속하면 NO를 반환한다.
     */
    lines.forEach((line) => {
      const [flag, a, b] = line.split(" ").map(Number);
      if (flag) console.log(find(set, a) === find(set, b) ? "YES" : "NO");
      else union(set, a, b);
    });
  });

트리 구조를 배열을 사용하여 구현했습니다. 배열의 인덱스는 노드를 의미하고, 배열의 값은 부모 노드를 의미합니다. 부모 노드를 가리키고 있는거죠. 예시와 함께 살펴보겠습니다.

input: 7 8         output: NO
       0 1 3               NO
       1 1 7               YES
       0 7 6
       1 7 1 -> 7과 1 찾기
       0 3 7
       0 4 2 -> 4와 2 합치기
       0 1 1
       1 1 1

0으로 시작하는 입력의 경우 합치기(union), 1로 시작하는 입력의 경우 찾기(find)를 통해 서로 같은 집합에 속해 있는 노드인지 확인하는 문제입니다. 위의 코드에서 makeSet은 각 노드가 각자의 집합을 가지게 만들어 반환하는 함수입니다. 각 노드는 해당 집합에서 유일하며, 곧 루트 노드가 됩니다. union을 통해 집합을 합할 수 있습니다. 두 집합의 루트 노드를 찾아가서 루트 노드를 합칩니다. find를 통해 현재 노드가 속한 집합의 루트 노드를 알 수 있습니다. a 노드와 b 노드의 루트 노드가 같으면, 같은 집합에 위치한다는 것을 알 수 있습니다.

[0,1,2,3,4,5,6,7] -> 초기화
[0,1,2,1,4,5,6,7] -> 3번 노드는 1번 노드를 부모 노드로 하여 연결된다.
NO
[0,1,2,1,4,5,6,7] 
[0,1,2,1,4,5,7,7] -> 6번 노드는 7번 노드를 부모 노드로 하여 연결된다.
NO
[0,1,2,1,4,5,7,7] 
[0,1,2,1,4,5,7,1] -> 7번 노드는 1번 노드를 부모 노드로 하여 연결된다. (6번 -> 7번 -> 1번)
[0,1,4,1,4,5,7,1] -> 2번 노드는 4번 노드를 부모 노드로 하여 연결된다.
[0,1,4,1,4,5,7,1] -> 1번 노드는 이미 루트 노드이므로 변화없다.
YES

매번 set을 찍어보면 다음과 같이 나옵니다. 위에 설명에도 나와있듯 배열의 인덱스와 값을 통해서 노드와의 관계를 표현할 수 있습니다.

슬프게도, 위의 코드를 돌려보면 시간 초과가 뜹니다. 그럼 이제 경로 단축 방법을 적용해봅시다.

/**
 * x가 속한 집합의 부모 노드를 반환한다.
 *
 * 인덱스와 값이 같아지면 루트 노드이다.
 * 배열의 값은 부모 노드를 가리키고 있으므로 이를 따라가면 루트 노드까지 도달할 수 있다.
 *
 * 매번 따라가는 건 비효율적일 수 있다.
 * 자식 노드가 부모 노드에 연결되어 있든, 루트 노드에 연결되어 있든 한 집합에 속하는 건 같다.
 * 자식 노드가 항상 루트 노드를 참조할 수 있도록 하면 더욱 효율적으로 탐색할 수 있다.
 */
function find(set, x) {
  if (set[x] === x) return x;
  set[x] = find(set, set[x]); // 부모 노드를 루트 노드로 변경한다.
  return set[x];
}

백준에서 set[x] = find(set, set[x]); 라인이 없으면 시간 초과가 발생합니다. 부모 노드를 따라가는 것이 아니라 탐색 작업에서 전부 부모 노드를 루트 노드로 바꿔줌으로써 보다 효율적으로 탐색하게끔 했습니다.

알고리즘 문제

프로그래머스: 2019 카카오 개발자 겨울 인턴쉽 - 호텔 방 배정
백준: 집합의 표현, 여행 가자

References

• geeksforgeeks disjoint set (or union-find)
• 서로소 집합 자료 구조