[이것이 취업을 위한 코딩 테스트다 with 파이썬] 8. 기타 그래프 이론

서로소 집합(Disjoint Sets) 자료구조 = 합치기 찾기(Union Find) 자료구조

• 서로소 집합: 공통 원소가 없는 두 집합
• 서로소 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조
• 2종류의 연산 지원
  • 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  • 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

동작 과정

• 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정

1. 합집합(Union) 연산을 확인 -> 서로 연결된 두 노드 A, B 확인
   1. A와 B의 루트 노드 A', B'를 각각 찾음
   2. A'를 B'의 부모 노드로 설정
2. 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정 반복

연결성

• 연결성 ~> 손쉽게 집합 형태를 확인
• 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 X
  • 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야 함

Python

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
	# 루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:
    	return find_parent(parent, parent[x])
    return 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

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
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)

# 각 원소가 속한 집합 출력
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=' ')

 

C++

Java

문제점

• 합집합(Union) 연산이 편향되게 이뤄지는 경우 찾기(Find) 함수가 비효율적으로 동작
• 최악의 경우: 찾기(Find) 함수가 모든 노드를 다 확인 -> 시간 복잡도: O(V)

경로 압축(Path Compression)

• 찾기(Find) 함수를 최적화하기 위한 방법
  • 찾기(Find) 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신

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

 

• 각 노드에 대하여 찾기(Find) 함수를 호출한 이후에 해당 노드의 루트 노드 -> 부모 노드가 됨
• 동일한 예시에 대해 모든 합집합(Union) 함수를 처리한 후 각 원소에 대해 찾기(Find) 함수로 수행 -> 부모 테이블 갱신
• => 기본적인 방법에 비해 시간 복잡도 개선

Python

# 특정 원소가 속한 집합을 찾기
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

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
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)

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

print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, v + 1):
	print(parent[i], end=' ')

---