---

Union-Find

: Disjoint set을 표현할 때 사용하는 알고리즘

Disjoint Set

: 서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조

➡️ 서로소 집합 자료구조

유니온 파인드는 트리구조를 이용하여 구현한다.

왜 트리구조를 이용하는가?

- 배열을 이용할 때

• Array[i]
  : i번 원소가 속하는 집합의 번호 (➡️ 루트 노드의 번호)
• make-set(x)
  : Array[i] = i와 같이 각자 다른 집합 번호로 초기화
• union(x, y)
  : 배열의 모든 원소를 순회하며 y의 집합 번호를 x의 집합 번호로 변경
  ➡️ 시간 복잡도 O(N)
• find(x)
  : 한 번에 x가 속한 집합 번호를 찾아냄
  ➡️ 시간 복잡도 O(1)

- 트리를 이용할 때

• 같은 집합 = 하나의 트리 ➡️ 집합 번호 = 루트노드
• make-set(x)
  : 각 노드는 모두 루트 노드이므로 N개의 로트 노드 생성 및 자기 자신으로 초기화
  ➡️ 시간 복잡도 O(N)보다 작으므로 find 연산의 시간복잡도를 따름
• find(x)
  : 노드의 집합 번호는 루트 노드이므로, 루트 노드를 확인하여 같은 집합인지 확인
  ➡️ 시간 복잡도는 트리 높이와 동일 (최악의 경우 O(N-1))

평균적인 시간복잡도는 트리의 높이만큼 탐색하게 되므로 O(logN)

Union-Find 연산

• make-set(x)
  - 초기화
  - x를 유일한 원소로 하는 새로운 집합을 생성
• union(x, y)
  - 합
  - x가 속한 집합과 y가 속한 집합을 합침
  ➡️ x와 y가 속한 두 집합을 합치는 연산
• find(x)
  - 찾기
  - x가 속한 집합의 루트 노드 값을 반환
  ➡️ x가 어떤 집합에 속해 있는지 찾는 연산

Union-Find 코드

int find(int x) {
    if(parent[x] == x) return x;

    return parent[x] = find(parent[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) return;

    parent[y] = x;

    /**
     * x와 y의 루트 노드가 같다면 같은 집합이므로 종료하고
     * 그게 아니라면 y의 부모를 x로 바꿈
     */
}

find = Find ➡️ 루트 노드를 찾는 함수, 루트에 도달할 때까지 부모노드로 거슬러 올라감
merge = Union ➡️ x 또는 y를 포함하는 부분 집합을 나타내는 트리를 다른 것의 부트리로 만들기

---

참고
참고
참고