[백준 2252번] 줄 세우기 : 위상 정렬(Topology Sort) - 파이썬(Python)

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

2252번: 줄 세우기

from collections import deque

def topology_sort(indegree, edge, n):
    result = [] # 큐에서 꺼낸 순서, 위상 정렬의 결과
    queue = deque()
    
    for i in range(1, n+1):
        if indegree[i] == 0: # 진입 차수가 0인 정점을 큐에 삽입한다.
            queue.append(i)
            
    while queue:
        current = queue.popleft() # 큐에서 원소를 꺼낸다.
        result.append(current)
        
        for i in edge[current]: # 원소와 연결된 모든 간선을 제거한다.
            indegree[i] -= 1
            if indegree[i] == 0: # 간선 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입힌다.
                queue.append(i)
                
    for i in result:
        print(i, end=' ')

def main():
    n, m = map(int, input().strip().split(' '))
    edge = [ [] for _ in range(n+1) ]
    indegree = [0] * (n+1)
    
    for _ in range(m):
        u, v = map(int, input().strip().split(' '))
        edge[u].append(v)
        indegree[v] += 1
        
    topology_sort(indegree, edge, n)

if __name__ == '__main__':
    main()

 

레퍼런스

https://m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)