[이것이 코딩 테스트다] 위상 정렬 알고리즘 with Python

📊위상 정렬

💡 위상 정렬이란 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다.

📊진입차수

특정한 노드로 들어오는 간선의 개수

만약 ‘알고리즘’이라는 과목이 2개의 선수과목을 가지고 있다면 ‘알고리즘’의 진입차수는 2이다.

📊위상 정렬 알고리즘

1️⃣ 진입차수가 0인 노드를 큐에 넣는다.

2️⃣ 큐가 빌 때까지 다음의 과정을 반복한다.

    2️⃣-1️⃣ 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.

    2️⃣-2️⃣ 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

💻 코드

from collections import deque

# 노드와 간선 개수 입력받기
v, e = map(int, input().split())

# 차수 저장 배열
indegree = [0] * (v+1)

# 그래프 정보 입력받기
graph = [[] for _ in range(v+1)]
for i in range(e):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    indegree[n2] += 1

# 결과를 담을 배열
result = []

# 큐 생성
queue = deque()

# 차수가 0이라면 큐에 삽입
for n in range(1, v+1):
    if indegree[n] == 0:
        queue.append(n)

# 큐가 빌 때까지 반복
while queue:
    # 현재 노드
    now = queue.popleft()
    # 결과에 추가
    result.append(now)
    # 현재 노드와 연결된 간선 제거
    for n in graph[now]:
        indegree[n] -= 1
        # 만약 차수가 0이 됐다면
        if indegree[n] == 0:
            # 큐에 삽입
            queue.append(n)

# 출력
for r in result:
    print(r, end=' ')

입력

7 8 1 2 1 5 2 3 2 6 3 4 4 7 5 6 6 4

출력

1 2 5 3 6 4 7