서로소 집합 (Disjoint Set)

• 서로소 집합 : 공통 원소가 없는 두 집합

• 서로소 집합 자료구조 (Union-Find)
  트리 구조를 사용하여 같거나 다른 집합으로 분리해주거나 최대 N개의 집합으로 분리할 수도 있다.

  • 합집합 (Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  • 찾기 (Find) : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산

기본적인 구현 방법

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

# 두 원소가 속한 집합을 합치기 
def union_parent(parent, a, b): #여기서 parent의 의미는?
	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 연산을 각각 수행 
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):
	pritn(parent[i], end=' ')

실행결과 :

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

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

• 합집합 연산이 편향되게 이루어질 경우 찾기 함수가 비효율적으로 동작함. → 최악에는 시간복잡도 O(V) : 모든 노드를 확인해야함

경로압축

• FIND 함수의 최적화 : FIND 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신한다.

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

👉FIND 함수를 호출한 이후, 해당 노드의 루트 노드가 바로 부모 노드가 됨.

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

• 무방향 그래프 내에서 사이클을 판별할 때 사용 가능

  • cf) 방향 그래프에서는 DFS를 이용하여 판별 가능

• 사이클 판별 알고리즘

  1. 각 간선에 연결된 두 노드의 루트노드 확인
     1) 루트 노드가 서로 다르다면 UNION
     2) 루트 노드가 서로 같다면 CYCLE 발생
  2. 그래프에 포함되어있는 모든 간선에 대해 1번 과정 반복

# 부모 테이블 초기화 이후

# 사이클 발생 여부 
cycle = False 

for i in range(e):
	a, b = map(int, input().split())
	# 사이클 발생하면 종료
	if find_parent(parent, a) == find_parent(parent, b) : 
		cycle = True
		break 
	#사이클 X -> 합집합
	else :
		union_parent(parent, a, b)

---

• 신장 트리 : 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
  • cf) 트리의 조건 : 모든 노드가 서로 연결, 사이클 X
    

크루스칼 알고리즘

: 최소 신장 트리(최소한의 비용으로 구성되는 신장 트리)를 찾는 방법

• 그리디 알고리즘 : 가장 짧은 간선부터 트리에 포함하고, 사이클을 만들면 제외
• 시간 복잡도 : $O(ElogE)$, E는 간선의 개수
  • 간선을 정렬할 때 걸리는 시간

1. 간선을 오름차순으로 정렬
2. 각 간선이 사이클을 발생시키는지 확인
   1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
   2) 사이클이 발생하는 경우 포함 X
3. 모든 간선에 대해 2번의 과정 반복

#부모테이블 초기화 이후

edges = []
result = 0

#간선 정보 입력받기
for _ in range(e) :
	a,b,cost = map(int, input().split())
	edges.append((cost, a, b))

#간선을 비용순으로 정렬
edges.sort()

#간선 하나씩 확인
for edge in edges : 
	cost, a, b = edge
	if find_parent(parent, a) != find_parent(parent, b):
		union_parent(parent, a, b)
		result += cost 

print(result)

위상정렬

: 사이클이 없는 방향그래프(DAG, Direct Acyclic Graph)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열

• 큐 이용
• 시간 복잡도 : 모든 노드 확인하며 차례대로 간선 제거 : $O(V+E)$

1. 진입 차수가 0인 모든 노드를 큐에 투입
2. 큐가 빌 때까지 아래 과정 반복
   1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

✔ 수행 결과 : 각 노드가 큐에 들어온 순서

• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단 가능
• 스택을 활용한 DFS를 활용할 수도 있음

from collections import deque

v, e = map(int, input().split())
indegree = [0]*(v+1)
graph = [[] for i in range(v+1)]

# 방향 그래프 간선정보 입력받기 
for _ in range(e):
	a, b = map(int, input().split())
	graph[a].append(b)
	indegree[b] += 1 #진입차수 1+

# 위상정렬 함수
def topology_sort():
	result = []
	q = deque()
	for i in range(1, v+1):
		if indegree[i] == 0 :
			q.append(i)
	while q: 큐가 빌 때까지 
		now = q.popleft() # 큐에서 원소 꺼내기
		result.append(now) 
		for i in graph[now]: # 해당 원소와 연결된 노드들의 진입차수 -1 
			indegree[i] -= 1
			if indegree[i] == 0:
				q.append(i)
                
	for i in result : 
		print(i, end=" ")

topology_sort()