12 / 14강

먼저 해야 할 일을 정하는 위상 정렬

앱을 배포하기 전에 테스트해야 하고, 테스트하기 전에 코드를 빌드해야 한다고 합시다. 위상 정렬은 선행 작업이 항상 뒤 작업보다 먼저 오도록 순서를 정하는 방법입니다.

빌드 → 테스트 → 배포에서 화살표는 먼저 끝내야 한다는 뜻입니다. 숫자나 이름순으로 정렬하는 것과 목적이 다릅니다.

시작할 수 있는 작업 찾기

정점으로 들어오는 간선 수를 진입 차수라고 합니다. 진입 차수가 0이면 아직 기다릴 선행 작업이 없습니다.

1. 진입 차수가 0인 작업을 큐에 넣습니다.
2. 큐에서 하나를 꺼내 결과에 추가합니다.
3. 그 작업 뒤에 오는 작업들의 진입 차수를 1씩 줄입니다.
4. 새로 0이 된 작업을 큐에 넣고 반복합니다.

이 방법을 칸(Kahn) 알고리즘이라고 합니다.

from collections import deque

graph = {"build": ["test"], "test": ["deploy"],
         "deploy": []}
indegree = {node: 0 for node in graph}
for neighbors in graph.values():
    for node in neighbors:
        indegree[node] += 1

ready = deque(node for node in graph if indegree[node] == 0)
order = []
while ready:
    node = ready.popleft()
    order.append(node)
    for neighbor in graph[node]:
        indegree[neighbor] -= 1
        if indegree[neighbor] == 0:
            ready.append(neighbor)

if len(order) != len(graph):
    raise ValueError("Cycle detected")
print(order)

출력은 ['build', 'test', 'deploy']입니다. 이 예제는 모든 정점을 딕셔너리의 키로 등록합니다. 나가는 간선이 없는 deploy도 빈 목록으로 둡니다.

사이클이 있으면 왜 안 될까요?

A 전에 B를, B 전에 A를 끝내야 한다면 둘 다 시작할 수 없습니다. 위상 정렬은 사이클이 없는 방향 그래프(DAG)에서 가능합니다. 큐가 비었는데 결과에 빠진 정점이 있다면 사이클이 존재합니다.

진입 차수가 0인 작업이 여러 개면 답도 여러 개일 수 있습니다. 인접 리스트 기준 시간은 O(V+E)입니다. 이 순서만으로 전체 작업 시간이 정해지지는 않습니다. 작업별 소요 시간과 동시에 실행할 수 있는 조건도 알아야 합니다.

확인 문제

밥 짓기와 반찬 만들기를 모두 끝낸 뒤 식사해야 합니다. 가능한 순서는 하나뿐일까요?