[백준] 2252번 파이썬 - 위상 정렬

문제요약 (2252. 줄 세우기)

키 순서가 주어질 때 키를 비교한 순서를 출력하라.

 

2252번: 줄 세우기

 

풀이를 위한 부연 설명

• 같은 순서가 나올 때 관계가 없이 출력된다는 점에서 위상 정렬이 사용된다.
  • 반드시 순환관계가 없는지 확인해야한다.
• 위상정렬에 대한 개념과 연관 문제는 다음 게시글을 참고하면 된다.

[코테 알고리즘] 그래프 이론 / 관련 문제

 

코드 

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())

student = [[] for _ in range(n+1)]
inDegree = [0] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    student[a].append(b)
    inDegree[b] += 1

que = deque()

for i in range(1, n+1):
    if inDegree[i] == 0:
        que.append(i)

while que:
    now = que.popleft()
    print(now, end=" ")
    for new in student[now]:
        inDegree[new] -= 1
        if inDegree[new] == 0:
            que.append(new)