썸네일 출처: 한국천문연구원
서로소 집합 (Disjoint Sets)
공통된 원소가 없는 두 집합. 서로소인 부분 집합들로 구성된 자료구조를 서로소 집합 자료구조라고 한다.
서로소 집합 자료구조에서는 union과 find 연산을 사용해 조작한다.
union(A, B): 2개의 집합을 하나로 합치기find(x): 특정 원소가 속한 집합이 어디인지 찾기
서로소 집합 자료구조를 구현할 때는 union 연산 중심으로, find 연산이 중간중간 수행되며 구현된다.
union(A, B)연산 입력- 입력된
union연산을 확인해서A와B를 확인 A, B각각의 루트 노드로A', B'을 찾는다(find).- 더 작은 값에 해당하는 노드를 부모 노드로 설정 (더 큰 값의 노드 -> 더 작은 값의 노드)
- 위 과정을 반복
그래프 관점에서, union(A, B)은 노드 A와 B를 간선(edge)로 연결한다는 의미로 해석할 수 있다.
반면, 루트 노드를 찾는 연산은 서로소 집합 자료구조에서 어느 집합에 속하는지를 알려주는 의미로 해석할 수 있다.
[서로소 집합 알고리즘의 기본 템플릿]
# find
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[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
for i in range(e):
a, b = map(int, input().split())
...사이클 판별
무방향 그래프 내에서의 사이클을 판별할 때 서로소 집합 자료구조를 활용할 수 있다.
각 간선을 확인하며 두 노드의 루트 노드를 확인했을 때, 두 노드의 루트 노드가 같다면 사이클이 발생한 것.
- 각 간선(
union)을 확인하며 두 노드의 루트 노드를 확인한다.
1-1. 루트 노드가 서로 다르면 그대로union연산 수행
1-2. 루트 노드가 서로 같다면 사이클이 발생한 것 - 1번의 과정을 모든 간선에 대해 반복
신장 트리
하나의 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프. 연결이 끊어진 노드가 있어도 안되고, 사이클이 발생해도 안됨.
한 그래프 내에서 여러 개가 존재할 수 있는데, 이 중 중 최소 비용은 크루스칼 알고리즘을 통해 찾을 수 있다.
크루스칼 알고리즘
기본적으로 그리디 알고리즘에 기반한다. 일단 비용(거리)을 기준으로 모든 간선을 정렬한 다음, 가장 낮은 간선부터 결과 집합에 포함시키면 되는데, 이때 사이클을 발생시키지 않는지를 판별해야 한다.
- 간선 데이터를 비용에 따라 오름차순으로 정렬
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
2-1. 사이클이 발생하지 않으면, 최소 신장 트리에 포함
2-2. 사이클이 발생하면, 최소 신장 트리에서 제외 - 모든 간선에 대해 2번의 과정을 반복
[크루스칼 알고리즘]
def find_parent(...):
def union_parent(...):
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블
for i in range(1, v + 1):
parent[i] = i
edges = []
result = 0
for _ in range(e):
a, b, cost = map(int, input().split())
edges.append((cost, a, b) # cost를 기준으로 정렬하기 위해 맨앞으로
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위상 정렬
일종의 정렬 알고리즘으로, 방향 그래프에서 모든 노드를 방향성에 거스르지 않고 순서대로 나열하는 것.
방향성이 존재하는 그래프를 대상으로 하기 때문에 in-degree에 대해 구별해야 한다. 특정 노드로 들어오는 간선의 개수를 의미하는 in-degree가 0인 노드부터 시작하는 것이 기본 규칙이다.
in-degree가 0인 노드를 큐에 넣는다.- 큐가 빌 때까지 다음 과정을 반복한다.
2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
2-2. 2-1을 통해in-degree가 0이 된 노드를 큐에 넣는다.
[위상 정렬]
from collections import deque
v, e = map(int, input().split())
indegree = [0] * (v + 1)
graph = [[] for i in range(v + 1)]
# 간선 정보를 입력 받아 인접행렬과 in-degree 값 초기화
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b) # 노드 A -> 노드 B
indegree[b] += 1
def topology_sort():
result = []
q = deque()
# 맨처음에는 in-degree가 0인 노드를 큐에 넣기
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]:
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
topology_sort()