위상정렬
- 그래프 이론에서 사용하는 정렬 방식으로 주로 사이클이 없는 방향 그래프에서, 정점들을 방향을 거스르는 간선없이 나열한다.
- 여러 작업들이 주어질 때 그 중 특정 작업을 마치기 위해 선행되어야 하는 작업들을 모두 정렬하는 테크닉
from collections import deque
v, e = map(int, input().split())
# 모든 노드에 대한 진입 차수는 0으로 초기화
indegree = [0] * (v + 1)
graph = [[] for _ in range(v + 1)]
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b)
# 진입차수를 1 증가
indegree[b] += 1
# 알고리즘 수행 결과를 담을 리스트
result = []
q = deque()
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, v + 1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
result.append(now)
# 해당 원소와 연결된 노드들의 진입차수에서 1씩 빼기
for nxt in graph[now]:
indegree[nxt] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[nxt] == 0:
q.append(nxt)
print(" ".join(map(str, result)))
유니온 파인드
- 서로시 집합을 표현하기 위한 자료구조로, 공통 원소가 없는 부분 집합들로 나누어진 원소 정보를 저장한다.
- 최소 스패닝 트리를 찾는 알고리즘은 크루스칼에서 사용하는 자료구조
Init
- n개의 원소가 각각의 집합에 포함되어 있도록 초기화
Union
- 두 원소 a, b가 주어질 때, 이들이 속한 두 집합(트리)을 하나로 합치는 연산
- 두 원소의 루트를 찾아서 하나를 다른 한쪽의 자손으로 넣는다.
- 두 트리를 합칠 때 항상 높이가 낮은 트리를 더 높은 트리 아래로 넣는 최적화 기법을 적용할 수 있다. (랭크에 의한 합치기)
Find
- 어떤 원소 a가 주어질 때, 이 원소가 속한 집합(트리의 루트)을 반환하는 연산
- find를 통해 찾아낸 원소의 루트를 미리 저장해두고, 다음 번의 호출에서 경로를 따라 올라갈 필요없이 바로 루트를 반환할 수 있도록 최적화할 수 있다. (경로 압축)
# 원소가 속한 집합의 루트 노드 찾기
# 경로 압축 기법: 파인드 함수를 재귀적으로 호출한 뒤에 부모 테이블값을 갱신
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
# 두 원소가 속한 집합 합치기
def union(a, b):
a = find(a)
b = find(b)
# 더 작은 쪽을 루트로 만든다.
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
# 부모를 자기 자신으로 초기화
parent = [i for i in range(v + 1)]
cycle = False
for i in range(e):
a, b = map(int, input().split())
# 사이클이 발생한 경우 종료
if find(a) == find(b):
cycle = True
break
# 사이클이 발생하지 않았다면 유니온 수행
union(a, b)
'Python > Algorithm' 카테고리의 다른 글
다이나믹 프로그래밍 (DP) (0) | 2022.03.04 |
---|---|
투 포인터와 슬라이딩 윈도우 (0) | 2022.03.04 |
버블 정렬, 선택 정렬, 삽입 정렬 (0) | 2022.03.01 |
트라이 (0) | 2022.02.27 |
힙과 우선순위 큐 (0) | 2022.02.27 |