알고리즘 - 11. Union-Find (서로소 집합 자료구조)

Union-Find를 사용하는 경우

Union-Find는 동적 그래프에서 연결성을 효율적으로 추적하거나 서로소 집합을 관리해야 할 때 사용합니다. 가장 일반적으로 연결 요소를 찾는 데 사용되지만, 다음과 같은 문제에도 적용할 수 있습니다:

그래프의 연결 요소 (고전적인 사용 사례)
무방향 그래프의 사이클 감지
최소 신장 트리를 찾는 크루스칼의 MST 알고리즘
네트워크 연결성 문제 (서버, 친구, 계정)
침투 문제 (물리 시뮬레이션, 미로 생성)
요소가 같은 그룹에 속하는지 효율적으로 확인하고 그룹을 병합해야 하는 모든 문제

예제 문제

소셜 네트워크: [[1,2], [2,3], [4,5], [6,7], [5,6]]와 같은 친구 관계 목록이 주어졌을 때, 다음을 효율적으로 답하세요:

사람 1과 사람 3이 친구입니까 (직접 또는 상호 연결을 통해)?
몇 개의 별도 친구 그룹이 존재합니까?
새로운 친구 관계가 형성될 때 두 친구 그룹을 병합할 수 있습니까?

모든 친구 관계를 처리한 후:

그룹 1: {1, 2, 3} - 친구 관계를 통해 모두 연결됨
그룹 2: {4, 5, 6, 7} - 친구 관계를 통해 모두 연결됨
총: 2개의 별도 친구 그룹

답: 사람 1과 3은 연결되어 있습니다 (같은 그룹), 총 2개의 그룹이 있으며, 네, 효율적으로 그룹을 병합할 수 있습니다.

Union-Find가 실제로 하는 일

Union-Find는 요소 그룹을 관리하는 자료구조입니다. 정확히 두 가지 연산을 제공합니다:

FIND: 요소가 어떤 그룹에 속하는지 결정 (그룹의 대표/루트를 반환)
UNION: 두 그룹을 하나의 그룹으로 병합

소셜 미디어에서 친구 서클을 관리하는 것과 같다고 생각하세요:

FIND: "앨리스는 어떤 친구 서클에 속해 있나요?"
UNION: "밥과 캐럴이 친구가 되었으니, 그들의 친구 서클을 병합하세요"

연산의 작동 방식

FIND 연산 - "이 요소는 어떤 그룹에 있습니까?"

find(5)를 호출하면:

요소 5에서 시작
루트까지 부모 포인터를 따라감 (루트는 그룹 식별자)
항상 루트를 반환 - 이 루트가 전체 그룹의 고유 ID 역할
최적화: 탐색하는 동안 경로를 압축하여 향후 조회를 빠르게 함

UNION 연산 - "이 두 그룹을 연결"

union(3, 7)을 호출하면:

요소 3의 그룹의 루트를 찾음
요소 7의 그룹의 루트를 찾음
같은 루트인 경우: 이미 연결되어 있으므로 아무것도 하지 않음
다른 루트인 경우: 한 루트가 다른 루트를 가리키도록 하여 즉시 전체 그룹을 병합

이러한 연산이 발생하는 시점

이러한 연산은 명시적으로 호출할 때만 발생합니다:

const uf = new UnionFind(10);

// UNION: 명시적으로 요소 연결
uf.union(1, 2); // 1과 2를 포함하는 그룹 연결
uf.union(2, 3); // 2와 3을 포함하는 그룹 연결

// FIND: 요소가 어떤 그룹에 속하는지 확인
let groupID = uf.find(3); // 항상 루트(그룹의 고유 ID)를 반환

// 일반적인 사용법: 두 요소가 연결되어 있는지 확인
uf.isConnected(1, 3); // 내부적으로 find(1)과 find(3)를 호출

Union-Find의 아름다운 점은 두 루트를 연결하는 것만으로 즉시 전체 그룹이 병합된다는 것입니다 - 각 그룹의 모든 요소를 업데이트할 필요가 없습니다!

가장 중요한 통찰

모든 요소는 정확히 하나의 부모를 가리키며, 집합을 나타내는 트리를 형성합니다 - 그리고 트리를 평평하게 만들고 (경로 압축) 트리 높이로 병합함으로써 (랭크에 의한 합집합), 대표 찾기와 집합 병합 모두에서 거의 상수 시간의 연산을 달성합니다.

멘탈 노트: 알고리즘의 천재성은 집합을 모든 요소가 결국 하나의 "루트" 대표를 가리키는 트리로 취급하는 데 있습니다. 각 연산에서 필요한 것은: (1) 부모 포인터를 따라 루트를 찾기 (향후 조회를 빠르게 하기 위해 압축과 함께), 또는 (2) 두 루트를 연결하여 전체 집합을 병합하기. 이 간단한 부모 포인터 메커니즘이 자동으로 서로소 집합을 효율적으로 유지합니다.

결정 프레임워크

Union-Find에는 두 가지 주요 결정이 포함됩니다:

Find 중 (경로 압축):

루트까지 부모 포인터를 따라감
노드가 직접 루트 (또는 조부모)를 가리키도록 경로를 압축

Union 중 (랭크에 의한 합집합):

두 요소의 루트를 찾음
다른 루트인 경우: 작은 트리를 큰 트리 아래에 붙임
같은 루트인 경우: 이미 연결되어 있으므로 아무것도 하지 않음

"트리 높이에 의한 병합"이 중요한 이유

랭크에 의한 합집합은 항상 짧은 트리를 긴 트리 아래에 붙여 트리를 최대한 평평하게 유지한다는 의미입니다. 이것이 중요한 이유는 다음과 같습니다:

랭크에 의한 합집합 없이 (나쁨):

항상 첫 번째 트리에 붙이면 체인이 생성됨:
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
높이: 8 (요소 8을 찾는 데 8단계가 걸림!)

랭크에 의한 합집합 사용 (좋음):

짧은 것을 긴 것에 붙이면 균형 잡힌 트리가 생성됨:
        1
      / | \
     2  3  6
    / \   / \
   4   5 7   8
높이: 3 (모든 요소를 최대 3단계로 찾을 수 있음!)

"랭크"는 트리의 높이입니다. 두 트리를 병합할 때:

한 트리가 더 높은 경우: 짧은 트리를 높은 트리의 루트 아래에 붙임
둘 다 같은 높이인 경우: 어느 쪽으로든 붙이지만, 결과 트리의 랭크를 1 증가시킴
결과: 최대 높이가 선형이 아닌 로그적으로 성장

이 최적화는 경로 압축 없이도 연산이 O(log n)으로 유지되도록 보장하며, 경로 압축과 함께 거의 상수 시간을 달성합니다!

코드

class UnionFind {
  constructor(numberOfElements) {
    // 부모 포인터 저장: parent[element] = element의 부모
    // 처음에 각 요소는 자기 자신의 부모 (즉, 루트를 의미)
    this.parent = new Map();

    // 트리 랭크 저장: rank[element] = 트리 높이의 상한
    // union 연산 중 트리를 균형 있게 유지하는 데 사용
    // 참고: 경로 압축 후, 이것은 실제 높이가 아닌 추정치가 됨!
    this.rank = new Map();

    // 초기화: numberOfElements개의 별도 그룹 생성
    // 각 요소는 자신의 그룹에서 시작 (자기 자신을 가리킴)
    for (let element = 1; element <= numberOfElements; element++) {
      this.parent.set(element, element); // 자기 루프는 "나는 루트다"를 의미
      this.rank.set(element, 0); // 단일 요소의 랭크는 0
    }
  }

  // FIND: 요소의 루트/그룹 ID를 반환
  // 또한 향후 연산을 빠르게 하기 위해 경로를 압축
  find(element) {
    // 요소에서 시작하여 부모 포인터를 위로 따라감
    let current = this.parent.get(element);

    // 루트를 찾을 때까지 트리를 계속 올라감
    // (루트는 parent[root] === root로 식별됨)
    while (current !== this.parent.get(current)) {
      // 결정 프레임워크: 경로 압축 최적화
      // 올라가는 동안 각 노드가 조부모를 가리키도록 함
      // 이는 트리 구조를 평평하게 만듦
      const parentOfCurrent = this.parent.get(current);
      const grandparent = this.parent.get(parentOfCurrent);
      this.parent.set(current, grandparent);

      // 다음 레벨로 이동
      current = this.parent.get(current);
    }

    // 루트에 도달 - 이것이 그룹 ID
    return current;
  }

  // UNION: element1과 element2를 포함하는 그룹을 병합
  // 병합된 경우 true 반환, 이미 같은 그룹인 경우 false 반환
  union(element1, element2) {
    // 단계 1: 각 요소가 어떤 그룹에 속하는지 찾기
    const root1 = this.find(element1);
    const root2 = this.find(element2);

    // 결정 프레임워크: 이미 연결되어 있는지 확인
    if (root1 === root2) {
      // 두 요소가 이미 같은 그룹에 있음
      return false;
    }

    // 단계 2: 루트를 연결하여 두 그룹을 병합
    // 결정 프레임워크: 랭크에 의한 합집합 - 트리를 균형 있게 유지
    const rank1 = this.rank.get(root1);
    const rank2 = this.rank.get(root2);

    if (rank1 > rank2) {
      // 트리 1의 랭크가 더 높음 - 균형을 유지하기 위해 부모로 만듦
      this.parent.set(root2, root1);
      // 랭크는 변경되지 않음 (작은 랭크 트리가 큰 랭크 트리에 붙음)
    } else if (rank1 < rank2) {
      // 트리 2의 랭크가 더 높음 - 균형을 유지하기 위해 부모로 만듦
      this.parent.set(root1, root2);
      // 랭크는 변경되지 않음 (작은 랭크 트리가 큰 랭크 트리에 붙음)
    } else {
      // 두 트리의 랭크가 같음 - 어느 쪽이든 부모로 선택
      this.parent.set(root1, root2);
      // 랭크가 1 증가 (두 개의 같은 랭크 트리가 병합됨)
      this.rank.set(root2, rank2 + 1);
    }

    return true; // 두 그룹을 성공적으로 병합
  }

  // 헬퍼: 두 요소가 같은 그룹에 있는지 확인
  isConnected(element1, element2) {
    // 요소들이 같은 루트를 가지면 연결되어 있음
    return this.find(element1) === this.find(element2);
  }
}

// === 사용 예제: 소셜 네트워크 문제 ===
// 7명의 사람이 있음 (1부터 7까지 번호 매김)
const socialNetwork = new UnionFind(7);

// 처리할 친구 관계 목록
const friendships = [
  [1, 2], // 사람 1과 2가 친구가 됨
  [2, 3], // 사람 2와 3이 친구가 됨 (이제 1,2,3이 모두 연결됨!)
  [4, 5], // 사람 4와 5가 친구가 됨
  [6, 7], // 사람 6과 7이 친구가 됨
  [5, 6], // 사람 5와 6이 친구가 됨 (이제 4,5,6,7이 모두 연결됨!)
];

// 각 친구 관계 처리 (친구 그룹 병합)
console.log("친구 관계 처리 중:");
for (const [person1, person2] of friendships) {
  const wasNewConnection = socialNetwork.union(person1, person2);
  if (wasNewConnection) {
    console.log(`사람 ${person1}과 ${person2}의 그룹을 연결했습니다`);
  } else {
    console.log(`사람 ${person1}과 ${person2}는 이미 같은 그룹입니다`);
  }
}

// 특정 사람들이 친구인지 확인 (직접 또는 간접적으로)
console.log("\n연결 확인:");
console.log(`1과 3이 친구입니까? ${socialNetwork.isConnected(1, 3)}`); // true
console.log(`1과 4가 친구입니까? ${socialNetwork.isConnected(1, 4)}`); // false
console.log(`4와 7이 친구입니까? ${socialNetwork.isConnected(4, 7)}`); // true

// 몇 개의 별도 친구 그룹이 존재하는지 세기
const uniqueGroups = new Set();
for (let person = 1; person <= 7; person++) {
  const groupID = socialNetwork.find(person);
  uniqueGroups.add(groupID);
}
console.log(`\n총 친구 그룹: ${uniqueGroups.size}`); // 2 그룹

의심 해소

일반적인 의심: "경로 압축은 트리 구조를 극적으로 변경하지만, 우리는 이후에 랭크를 업데이트하지 않습니다. 신중하게 유지한 랭크를 망치지 않을까요? 이것은 버그가 아닌가요?"

이것은 심각한 불일치처럼 보입니다 - 우리는 트리를 균형 있게 유지하기 위해 랭크를 사용하지만, 경로 압축은 랭크를 업데이트하지 않고 트리를 평평하게 만듭니다. 이 명백한 "버그"가 실제로는 뛰어난 설계 결정인 이유를 탐구해 봅시다.

이것이 잘못된 것처럼 보이는 이유

경로 압축으로 무슨 일이 일어나는지 고려해 보세요:

find(5) 전:                 경로 압축 후 find(5):
    1 (랭크=3)                   1 (랭크=3 - 변경 없음!)
    |                           /|\\
    2 (랭크=2)                  2 3 4 5
    |
    3 (랭크=1)
    |
    4 (랭크=0)
    |
    5 (랭크=0)

실제 높이: 5                  실제 높이: 2
저장된 랭크: 3                저장된 랭크: 여전히 3!

트리가 높이 5에서 높이 2로 변했지만 랭크는 3으로 유지됩니다. 이것은 완전히 잘못된 것처럼 보입니다!

핵심 통찰: 랭크는 높이에 대해 의미가 없어짐

중요한 깨달음은 다음과 같습니다: 경로 압축이 시작되면 랭크는 실제 트리 높이와 완전히 분리됩니다.

랭크는 완전히 틀릴 수 있습니다 - 추정치조차 아닙니다:

랭크 10의 트리가 실제 높이 1을 가질 수 있음 (공격적인 압축 후)
랭크 3의 트리가 실제 높이 3을 가질 수 있음 (압축되지 않은 경우)
랭크는 현재 구조에 대해 아무것도 알려주지 않음

왜 랭크를 업데이트할 필요가 없는가

1. 랭크는 한 가지에만 사용됨: union 중 부모 선택

// 랭크가 중요한 유일한 곳:
if (rank1 > rank2) {
  parent[root2] = root1; // 더 높은 랭크가 부모가 됨
}

어떤 루트가 부모가 될지 결정하면, 각 트리의 내부 구조는 향후 union에 영향을 주지 않습니다 - 루트의 랭크만 중요합니다.

2. 경로 압축은 루트가 아닌 노드에만 영향을 줌

압축 전:              압축 후:
    1 (랭크=2)           1 (랭크=2)
    |                   /|\
    2                  2 3 4
    |
    3
    |
    4

노드 1은 여전히 루트!
노드 1의 랭크는 union 결정에 여전히 유효!
노드 2,3,4는 어쨌든 의미 있는 랭크가 없음 (루트가 아님)

3. 완전히 잘못된 랭크도 최악의 경우를 방지함

놀라운 부분은 - 랭크가 완전히 틀려도 여전히 도움이 된다는 것입니다:

트리 A (랭크=10, 대규모 압축 후 실제 높이=1):
    A
   /|\\...
  (50개의 노드가 모두 직접 자식)

트리 B (랭크=2, 실제 높이=2):
    B
    |
    C
    |
    D

Union(A,B) → B가 A 아래에 붙음 (랭크 10 > 랭크 2)

왜 이것이 여전히 도움이 되는가:
- 트리 A는 어느 시점에 높았기 때문에 랭크 10을 가짐
- 많은 트리를 흡수하여 그 랭크를 얻음
- 지금은 평평하지만, 더 많은 노드를 가질 가능성이 높음
- 작은 트리를 큰 트리(노드 수 기준)에 붙이는 것은 여전히 좋음!

핵심 통찰: 랭크는 높이에 대해 완전히 틀려도 트리 크기(노드 수)와 우연히 상관관계가 있습니다!

이것을 수학적으로 증명할 수 있나요?

실제로 네! 랭크와 최소 노드 수 사이에 수학적 관계가 있습니다:

정리: 랭크 r의 트리는 최소 2^r개의 노드를 포함합니다.

귀납법에 의한 증명:

기본 경우: 랭크 0 = 단일 노드 = 2^0 = 1개 노드 ✓
두 개의 랭크 r 트리를 병합할 때: 랭크 r+1에 최소 2^r + 2^r = 2^(r+1)개 노드를 얻음 ✓
경로 압축은 랭크를 변경하거나 노드를 제거하지 않음
따라서: 랭크 r → 최소 2^r개 노드는 항상 성립

예시:

랭크 10의 트리 → 최소 2^10 = 1,024개 노드
랭크 2의 트리 → 최소 2^2 = 4개 노드
따라서 랭크 2 트리를 랭크 10 트리 아래에 붙이는 것이 타당함!

왜 작은 랭크를 큰 랭크에 붙이는 것이 최적인가:

최대 가능한 find() 경로 길이에 무슨 일이 일어나는지 고려해 보세요:

옵션 A: 랭크 2 트리를 랭크 10 트리 아래에 붙임

랭크 10 트리의 노드: 경로 변경 없음
랭크 2 트리의 노드: 경로가 1 증가
가장 영향받음: 최대 2^2 = 4개 노드가 더 긴 경로를 가짐
총 "비용": 4개 노드 × 1 추가 단계 = 4 단위

옵션 B: 랭크 10 트리를 랭크 2 트리 아래에 붙임

랭크 2 트리의 노드: 경로 변경 없음
랭크 10 트리의 노드: 경로가 1 증가
가장 영향받음: 최소 2^10 = 1,024개 노드가 더 긴 경로를 가짐
총 "비용": 1,024개 노드 × 1 추가 단계 = 1,024 단위

수학적 결론:

옵션 A는 ≤ 4개 노드에 부정적 영향
옵션 B는 ≥ 1,024개 노드에 부정적 영향
옵션 A는 옵션 B보다 256배 더 좋음!

가장 중요한 것은, 이것이 최악의 시나리오를 방지합니다:

랭크에 의한 합집합이 없으면, 높이 n의 n개 요소 체인을 만들 수 있습니다:

1 → 2 → 3 → 4 → ... → n (높이 = n, find() = O(n))

랭크에 의한 합집합으로, 최대 높이는 로그적입니다:

최대 높이 ≤ log₂(n)
n개 노드를 가진 트리 → 랭크 ≤ log₂(n) → 높이 ≤ log₂(n)

이 보장이 유지되는 이유:

랭크 r을 얻으려면 두 개의 랭크 r-1 트리를 병합해야 함
각 랭크 증가는 최소 노드 수를 두 배로 만듦
따라서: n개 노드 → 최대 랭크 = log₂(n)
경로 압축 없이도 find()는 O(n)이 아닌 O(log n)!

이것이 랭크에 의한 합집합이 작동하는 이유입니다: 선형 체인을 방지하고 총 경로 길이를 최소화합니다. 랭크가 높이에 대해 "틀렸더라도", O(n) 연산으로의 최악의 경우 성능 저하를 방지하는 것에 대해서는 "맞습니다"!

구체적인 예: 랭크를 업데이트하는 것이 비싸고 불필요한 이유

모든 경로 압축 후 랭크를 업데이트한다면 상상해 보세요:

find(deepElement) {
  // ... 경로 압축 수행 ...

  // 이제 우리는 다음을 해야 합니다:
  // 1. 실제 높이를 찾기 위해 전체 트리 탐색
  // 2. 루트의 랭크 업데이트
  // 3. 이것은 O(α(n))을 O(n)으로 만듦 - 끔찍함!
}

랭크를 업데이트하려면 각 압축 후 전체 트리 구조를 검사해야 합니다 - 이것은 우리가 열심히 달성한 거의 상수 시간 복잡도를 파괴할 것입니다!

이 "고장난" 시스템이 실제로 작동하는 이유

뛰어난 통찰은 정확한 높이가 전혀 필요하지 않다는 것입니다. 이유는 다음과 같습니다:

랭크는 트리 크기의 대리자가 됨 - 수학적으로 증명됨: 랭크 r은 ≥ 2^r개 노드를 보장
높은 랭크 = 기하급수적으로 많은 노드 - 랭크 10은 랭크 2보다 256배 많은 노드를 가짐 (최소)
작은 것을 큰 것에(노드 수 기준) 붙이면 트리가 균형을 유지 - 그리고 랭크가 이를 달성함!
경로 압축이 모든 것을 수정 - union이 완벽하지 않아도 압축이 모든 경로를 평평하게 만듦

아름다운 역설

랭크가 높이 측정으로서 완전히 의미가 없어지는 것을 받아들임으로써:

비싼 높이 재계산을 피함 (O(α(n)) 복잡도 유지)
랭크는 여전히 union 결정에 유용한 휴리스틱을 제공 (크기와의 상관관계를 통해)
경로 압축이 나쁜 결정을 커버
랭크가 "틀렸음에도" 두 최적화가 함께 작동

결론: 랭크가 실제 높이와 완전히 분리되는 것은 버그가 아니라 기능입니다! 알고리즘은 실제로 정확한 높이가 필요하지 않기 때문에 작동합니다. 랭크는 트리 크기와 우연히 상관관계가 있는 과거 병합의 "화석 기록" 역할을 하며, 경로 압축과 결합될 때 충분합니다.