백준 2252 줄 세우기 - 파이썬

문제.

풀이.

위상 정렬은 사이클이 없고 방향만 존재하는 그래프에서 정점을 나열하는 방법이다.

정점간의 연결관계를 저장한 리스트와 정점으로 들어오는 그래프 개수를 저장하는 리스트를 만든다.

그리고나서 진입 루트가 0 즉 자기 자신으로 들어오는 그래프 개수가 0인 정점들을 큐에 저장하고

해당 정점과 연결되어 있는 노드에서 진입 루트 개수를 하나씩 빼준다.

이렇게 계속 반복하면 된다.

 

소스코드.