CHAPTER 10. 그래프 이론 - 서로소 집합

서로소 집합

공통 원소가 없는 두 집합을 의미

• 예를 들어, {1, 2}와 {3, 4}는 서로소 관계인 반면 {1, 2}와 {2, 3}은 2가 공통원소이므로 서로소 관계가 아니다.

서로소 집합 자료구조

서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

• 몇몇 그래프 알고리즘에서 사용된다.
• union, find 2개의 연산으로 동작한다.
• union(합집합) 연산: 원소가 포함된 집합 2개를 하나의 집합으로 합치는 연산
• find(찾기) 연산: 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산'

서로소 집합 계산 알고리즘

1. 트리 자료구조를 이용하여 집합을 표현
2. 노드 개수(V) 크기의 부모 테이블을 초기화
3. 서로소 집합 정보가 주어짐
4. union 연산으로, 서로 연결된 두 노드 A,B를 확인
   1. A와 B의 루트노드 A', B'를 각각 찾는다.
   2. A'를 B'의 부모 노드로 설정한다.
      • 이때, 더 작은 원소가 부모 노드가 되도록 한다.
      • A' < B'라면 B'가 A'를 가리키도록 한다.
      • 부모 테이블 갱신
5. 모든 union 연산을 처리할 때까지 3번 과정을 반복

• 연결성을 통해 집합의 형태를 확인할 수 있다.
• 같은 집합인지 보려면 부모 테이블을 통해 루트 노드를 찾아야 한다.(재귀적으로 부모를 거슬러 올라감)

구현

방법1. 기본적인 서로소 집합 알고리즘

# 특정 원소가 속한 집합 찾기 (루트 노드를 찾는 함수)
def find_parent(parent, node):
  # 루트노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
  if parent[node] != node:
    return find_parent(parent, parent[node]) 
  return node # 특정 원소가 속한 집합의 루트 노드 번호 반환

# 두 원소가 속한 집합 합치기
def union_parent(parent, a, b):
  a = find_parent(parent, a) # 노드 a의 루트노드 찾기
  b = find_parent(parent, b) # 노드 b의 루트노드 찾기
  # 루트 번호를 비교해서 큰쪽이 작은 쪽을 가리키도록 연결
  if a < b:
    parent[b] = a
  else:
    parent[a] = b
    
v, e = map(int, input().split()) # 노드의 개수 v와 간선의 개수(union 연산) e 입력받기
parent = [0] * (v+1) # 부모 테이블 초기화

# 부모 테이블에 부모를 자기 자신으로 초기화
for i in range(1, v+1):
	parent[i] = i

# union 연산 수행, 간선 개수에 따라서 연결 여부 확인
for i in range(e): 
  a, b = map(int, input().split())
  union_parent(parent, a, b) # 노드 a, b에 대해서 union

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합:', end = ' ')
for i in range(1, v+1):
  print(find_parent(parent, i), end=' ') # 실제로는 루트 노드 출력, 루트노드가 같은 원소끼리는 같은 집합이다.

print()

# 부모테이블 내용 출력, 부모에 대한 정보, 루트는 아님
print('부모 테이블:', end = ' ')
for i in range(1, v+1):
  print(parent[i], end = ' ')

각 원소가 속한 집합: 1 1 1 1 5 5 
부모 테이블: 1 1 2 1 5 5

• 루트 노드가 같은 원소끼리는 동일한 집합을 이룸 → {1, 2, 3, 4} {5, 6}으로 나누어짐

시간 복잡도

• 하지만, 위의 코드는 find 함수가 비효율적임 → 최악의 경우 모든 노드를 확인하므로 시간 복잡도는 $O(V)$
  • 예를 들어, 1 ← 2 ← 3 ← 4 ← 5로 연결된 경우
  • 5의 루트를 찾기위 해서는 모든 노드를 거슬러 올라가야하므로 최대 $O(V)$의 시간이 소요된다.
• 따라서 위 코드는 노드 개수 V개, find 혹은 union 연산 개수 M개일 때 전체 시간 복잡도가 $O(VM)$으로 비효율적임

그렇다면 find 함수를 최적화해보자! 경로 압축 기법으로 시간 복잡도를 개선할 수 있다.

경로 압축 기법

• find 함수를 재귀적으로 호출한 뒤 부모 테이블 값을 갱신하는 방법
• find 함수 호출 이후 해당 노드의 부모 테이블 값은 루트노드가 된다.
  • 즉, 동일한 연산에 대해서 2, 3, 4, 5의 부모테이블의 부모 노드는 모두 1이 된다.
• 루트 노드에 더 빨리 접근 가능하므로 시간 복잡도가 개선됨

# 경로 압축 기법 소스코드
def find_parent(parent, node):
  if parent[node] != node:
    parent[node] = find_parent(parent, parent[node]) # 루트 노드를 찾을 때 까지 재귀적으로 호출
  return parent[node] # 자신의 루트를 찾음

6 4
1 4
2 3
2 4
5 6
각 원소가 속한 집합: 1 1 1 1 5 5 
부모 테이블: 1 1 1 1 5 5

시간 복잡도

 노드 개수 V개, 최대 V-1개의 union 연산, M개의 find 연산인 경우 경로 압축 방법을 이용했을 때 시간 복잡도는 $O(V+M(1+log_{2-M/V}V))$라고 알려져 있다. (교재에서 증명과정은 생략함)