[백준] 2252 줄세우기 in python + 위상정렬(topology_sort)

위상 정렬만 알면 날먹 가능한 문제이다

https://www.acmicpc.net/problem/2252

학생들을 줄 세워야 하는데 우선순위의 일부분이 m개 주어진다

이를 위상정렬 그래프로 생각하면 반드시 정점 a(학생1) 을 먼저 방문한 이후,  정점 b(학생2) 를 방문해야 한다 라는 순서가 된다. 

위상정렬에서는 정점 b를 가기 위해서는 반드시 정점 a를 지나쳐야 하므로, 진입차수(indegree)가 1 증가하게 된다. 

# 위상 정렬

from collections import deque

v, e = map(int, input().split())

indegree = [0]*(v+1) # 진입 차수
graph = [[] for _ in range(v+1)]

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

def topology_sort():
    result = []
    q = deque()

    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i, end=' ') # 위상 정렬의 결과 수행
topology_sort()