동빈나님의 27강 - 위상정렬을 보고 정리한 내용입니다.
순서가 정해진 작업을 차례대로 수행할때 그 순서를 알기 위해 사용하는 알고리즘
queue를 사용하는 방법과 stack을 사용하는 방법이 있는데 queue를 사용하는 방법을 알아보자.
백준 1005 - ACM craft의 예시로 살펴보자.
진입차수가 0인 노드를 queue에 삽입한다.
-> 진입차수란? 해당 node로 들어오는 간선의 개수 즉, node를 만족하는 조건의 개수이다.
예시에서 각 노드의 진입차수는 아래와 같다.
진입차수가 0인 노드1을 큐에 삽입한다.
queue에서 원소를 꺼내서 해당 원소와 연결된 모든 간선을 제거한다.
진입차수가 0이 된 정점을 queue에 삽입한다.
-> 여기서는 노드 2와 3이 진입차수가 0이 된 정점이다.
queue가 빌때까지 2,3을 반복한다.
-> 모든 원소를 방문하기 전에 queue가 비면 cycle이 존재해서 위상정렬을 수행할 수 x, 아니면 queue에서 꺼낸 순서가 위상정렬을 수행한 순서가 된다.
위의 예제를 이 알고리즘대로 수행하면 아래와 같은 순서로 진행된다.
모든 원소를 방문한 후에 queue가 비었고, 이때 queue에서 꺼낸 순서 1,2,3,4가 위상정렬을 한 결과가 된다.
from collections import deque
#indegree[i] : i의 진입 차수
#answer = [] : 위상정렬의 결과가 담긴 배열
def topologiSort():
queue = deque()
# 1. 진입차수가 0인 노드 전부 queue에 넣기
for i in range(N):
if indegree[i] == 0:
queue.append(i)
# 위상정렬 수행하기
for i in range(N):
# 모든 노드 방문 전에 큐가 비면 -> cycle이 있는 그래프
if not queue:
return False
current = queue.popleft()
answer.append(current) #위상정렬 결과 리스트에 추가
# 2. 인접한 정점 순회하면서 간선 제거하기
for next in adj[current]:
indegree[next] -= 1
# 3. 진입차수 0인 node queue에 넣기
if indegree[next] == 0:
queue.append(next)
return True