실생활에서 가장 찾기 쉬운 예시는 교과 이수 제도이다. 대학교에는 선수과목이 있는 과목들이 있다. 예를들어 프로그래밍1을 들어야 프로그래밍2를 들을 수 있는 것처럼.
만약 이런 선수과목이 있는 여러 과목들이 주어졌을 때 모든 과목을 수강하고 싶다면 어떤 순서로 과목을 들어야 할까?
위상정렬이란 방향그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬이다. 만약 그래프 안에 사이클이 존재할 경우에는 올바른 위상정렬이 존재할 수 없다.
우선 다른건 고민하지 말고 정점중에서 indegree가 0인(방향이 자신에게 향해 있는 정점이 없는) 정점을 먼저 찾아준다.
찾았다면 위상정렬 결과에 그 정점을 담아주고 정점을 제거해준다. 제거한 후 다시 indegree가 0인 정점을 찾아주고 위 행동을 반복해주면 된다.
각 정점은 큐에 최대 한 번 들어가고 indegree를 감소시키는 연산은 각 간선에 대해 1번씩만 발생하기 때문에 시간복잡도는 O(V+E)이다.
from collections import deque, defaultdict
N = 7
graph = defaultdict(list)
indegrees = [0] * (N+1)
for _ in range(N):
node1, node2 = input().split()
node1, node2 = ord(node1) - ord("A") +1, ord(node2) - ord("A") + 1
graph[node1].append(node2)
indegrees[node2] +=1
zero_indegree_queue = deque()
topological = []
for i in range(1, N+1):
if indegrees[i] == 0:
zero_indegree_queue.append(i)
while zero_indegree_queue:
cur_node = zero_indegree_queue.popleft()
topological.append(chr(cur_node+ord("A")-1))
for next_node in graph[cur_node]:
indegrees[next_node] -= 1
if indegrees[next_node] == 0:
zero_indegree_queue.append(next_node)
print(graph)
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
sorted_height = []
node_indegrees = [0] * (N+1)
graph = defaultdict(list)
zero_indegree_queue = deque()
for _ in range(M):
node1, node2 = map(int, input().split())
graph[node1].append(node2)
node_indegrees[node2]+=1
for i in range(1, N+1):
if node_indegrees[i] == 0:
zero_indegree_queue.append(i)
while zero_indegree_queue:
cur_node = zero_indegree_queue.popleft()
sorted_height.append(cur_node)
for next_node in graph[cur_node]:
node_indegrees[next_node]-=1
if node_indegrees[next_node] == 0:
zero_indegree_queue.append(next_node)
print(*sorted_height)