October 10, 2021

서로소 집합

서로소 집합(Disjoint Set)이란 공통 원소가 없는 두 집합을 의미한다.

서로소 집합 자료구조

• 서로소 부분 집합들이 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.
• 서로소 집합 자료구조는 두 종류의 연산을 지원한다.
  • Union : 두 개의 원소가 포함된 잡합을 하나의 집합으로 합치는 연산이다.
  • Find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.
• 서로소 집합 자료구조는 UnionFind 자료구조라고 불리기도 한다.

서로소 집합 자료구조 동작 과정

여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작과정은 다음과 같습니다.

1. Union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
   1. A와 B의 루트 노드 A', B'을 각각 찾는다.
   2. A'을 B'의 부모 노드로 설정한다.
2. 모든 Union 연산을 처리할 때까지 1번의 과정을 반복한다.

기본적인 구현 방법의 문제점

• Union 연산이 편향되게 이루어지는 경우 Find 함수가 비효율적으로 동작한다.
• 최악의 경우에는 찾기 함수가 모든 노드를 다 확인하게 되어 시간 복잡도가 O(V)이다.

경로 압축

• Find 함수를 최적하하기 위한 방법으로 경로 압축을 이용할 수 있다.
  • Find 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신한다.

서로소 집합을 활용한 사이클 판별

• 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.
  • 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있다.
• 알고리즘 동작 과정
  1. 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다.
     1. 루트 노드가 서로 다르다면 두 노드에 대하여 Union 연산을 수행한다.
     2. 루트 노드가 서로 같다면 Cycle이 발생한 것이다.
  2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.