위상정렬 - 바킹독

알고리즘 설명

실생활에서 가장 찾기 쉬운 예시는 교과 이수 제도이다. 대학교에는 선수과목이 있는 과목들이 있다. 예를들어 프로그래밍1을 들어야 프로그래밍2를 들을 수 있는 것처럼.

만약 이런 선수과목이 있는 여러 과목들이 주어졌을 때 모든 과목을 수강하고 싶다면 어떤 순서로 과목을 들어야 할까?

위상정렬이란 방향그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬이다. 만약 그래프 안에 사이클이 존재할 경우에는 올바른 위상정렬이 존재할 수 없다.

알고리즘 구현

우선 다른건 고민하지 말고 정점중에서 indegree가 0인(방향이 자신에게 향해 있는 정점이 없는) 정점을 먼저 찾아준다.

찾았다면 위상정렬 결과에 그 정점을 담아주고 정점을 제거해준다. 제거한 후 다시 indegree가 0인 정점을 찾아주고 위 행동을 반복해주면 된다.

구현의 편의를 위한 성질

1. 정점과 간선을 실제로 지울 필요 없이 미리 Indegree의 값을 저장했다가 매번 뻗어나가는 정점들의 indegree 값만 1 감소 시켜도 과정을 수행가능
2. indegreerk 0인 정점을 구하기 위해 매번 모든 정점들을 다 확인하는 대신 목록을 따로 저장하고 있다가 직전에 제거한 정점에서 연결된 정점들만 추가

위상 정렬 알고리즘

1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채움
2. indegree가 0인 정점들을 모두 큐에 넣음
3. 큐에서 정점을 꺼내어 위상 정렬 결과에 추가
4. 해당 정점으로부터 연결된 모든 정점의 indegree값을 1 감소시킴 이 때 indegree가 0이 되었다면 그 정점을 큐에 추가
5. 큐가 빌 때까지 3,4 과정을 반복

구현코드

각 정점은 큐에 최대 한 번 들어가고 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)