파이썬 백준 2252 줄 세우기

import sys input = sys.stdin.readline from collections import deque Vn, En = map(int, input().split()) parent = [0 for i in range(Vn + 1)] V = [[] for i in range(Vn + 1)] for i in range(En) :     big, small = map(int, input().split())     V[big].append(small)     parent[small] = parent[small] + 1 que = deque() for i in range(1, Vn + 1) :     if parent[i] == 0 :         que.append(i) while que :     now = que.popleft()     print(now, end = ' ')     for next in V[now] :         parent[next] = parent[next] - 1         if parent[next] == 0 :             que.append(next)

위상정렬하고자 하는 value의 우선도에 따라 점간의 외방향 연결을 기록한다.

완성된 기록을 통해 부모가 몇 있는지 기록하는 리스트 parent를 만든다.

부모가 0인 점들을 que에 담아 BFS를 실행하고, while문 내에서 그 점의 자식의 parent값을 -1하며 0이라면 큐에 넣는다.

이런 식으로 매 순간 부모가 없는 노드에 대해 연산을 실행함으로써 위상정렬된 순서로 연산하는 것이 가능하다.

문제에서는 위상정렬하고자 하는 value가 학생의 키이고, 이 대소관계를 기록한 리스트를 통해 부모가 없는 학생(?)을 차례대로 출력함으로써 키순 정렬을 구현했다.