[알고리즘] 서로소 집합 자료구조 (feat. Union-Find, Python)

Woonil·2025년 2월 11일

알고리즘

목록 보기

29/42

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

개념

서로소 집합 자료구조

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

특징
- 각 집합이 어떤 원소를 공통으로 가지고 있는 지를 확인할 수 있다.
- union과 find 두 연산으로 조작할 수 있다. (스택과 큐 자료구조에 push와 pop 두 연산으로 이루어지는 것과 비슷하다.)
  - union연산: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  - find 연산: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
- 부모 테이블은 말 그대로 부모에 대한 정보만을 담고 있다. (경로압축 기법을 사용하면 union, find 수행 후 부모 테이블의 값은 루트노드로 갱신된다.) ⇒ 실제로 루트를 확인하고자 할 때는 재귀적으로 부모를 거슬러 올라가서 최종적인 루트 노드를 찾아야한다.

과정

트리 자료구조를 이용하여 집합을 표현한다.
union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
1. A와 B의 루트 노드 A’, B’를 각각 찾는다.
2. A’를 B’의 부모 노드로 설정한다. (B’가 A’를 가리키도록 한다.)
모든 union(합집합) 연산을 처리할 때까지 위 과정을 반복한다.

구현

python 구현

find 연산 정의

루트 노드는 부모테이블에 자기 자신을 담고 있다.

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

union 연산 정의

# 두 원소가 속한 집합 합치기
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

입력값 받기

# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())

부모테이블 초기화

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

union 연산 수행

# union 연산 각각 수행
for i in range(e):
  a, b = map(int, input().split())
  union_parent(parent, a, b)

find 연산으로 집합 찾기

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
  print(find_parent(parent,i), end=' ')

find 최적화

경로 압축

위와 같은 코드로 구현 시 find 함수가 비효율적으로 동작한다 . 왜냐하면 최악의 경우 find 함수가 모든 노드를 다 확인하게 되어, 노드의 개수가 N이고 find 혹은 union 연산의 개수가 M일 경우는 시간 복잡도가 O(VM)가 될 수 있기 때문이다.

⇒ 경로압축 기법으로 최적화할 수 있다. (find 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 갱신한다.)

각 노드에 대하여 find 함수를 호출한 이후에, 해당 노드의 루트 노드가 바로 부모 노드가 된다. 즉, 트리의 구조를 변경함으로써 높이를 최소화하는 것이다. 결국 더 적은 간선을 타고 루트로 도달할 수 있으므로 시간복잡도가 줄어든다.

def find_parent(parent, x):
	if parent[x] != x:
		# 즉시 부모테이블을 갱신함
		**parent[x] = find_parent(parent, parent[x])**
	return **parent[x]**

... 나머지 코드는 기존 코드와 동일 ...

# 부모 테이블 내용 출력 - 기존 코드와 다르게 루트노드가 부모노드로 설정됨
print('부모 테이블: ', end='')
for i in range(1, v + 1):
  print(parent[i], end=' ')

사이클 판별

무방향 그래프 내의 사이클을 판별할 때 서로소 집합이 사용될 수 있다.

cf) 방향 그래프 내의 사이클 판별에는 DFS가 사용될 수 있다.

각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
1. 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
2. 루트 노드가 서로 같다면 사이클이 발생한 것이다.
그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
	if parent[x] != x:
		parent[x] = find_parent(parent, parent[x])
	return parent[x]

# 두 원소가 속한 집합 합치기
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())

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

cycle = False # 사이클 발생 여부

# 각 간선에 대해 union 연산 수행
for i in range(e):
  a, b = map(int, input().split())
  # 사이클이 발생한 경우 종료
  if find_parent(parent, a) == find_parent(parent, b):
    cycle = True
    break
  # 사이클이 발생하지 않았다면 합집합(union) 수행
  else:
    union_parent(parent, a, b)