이번 문제는 자신의 뒤에 서는 학생을 리스트로 가지는 그래프를 인접 리스트 형식으로 구현하고, 자신의 앞에 있는 학생의 수를 세는 리스트를 따로 만든 뒤, 이 두 개의 리스트를 사용하여 BFS 방식으로 탐색하여 해결하였다.

우선 자신의 앞에 있는 학생의 수가 0인 학생들을 큐에 모두 넣고, BFS 내부에서 큐에서 나온 학생 뒤에 서있는 학생에 대하여 그 학생 앞에 서있는 수를 1 감소시키고, 만약 앞에 서있는 수가 0이 되면 그 학생을 큐에 넣도록 하였고, 이 과정이 끝나면 큐에서 나온 학생은 정답 리스트에 들어가도록 하였다.

이 방법을 사용하면 자신의 앞에 아무도 없는 학생들부터 순서대로 정답 리스트에 들어가고 이때마다 이 학생의 뒤에 있는 학생들의 앞에 있는 수가 1씩 감소하게 되고, 결론적으로는 모든 학생이 정답 리스트에 들어가게 된다.

• 정답을 저장할 리스트 answer를 선언한다.
• n, m을 입력받는다.
• 학생들의 서있는 정보를 입력받을 리스트 arr을 선언한다.
• graph를 인접 리스트로 선언한다.
• cnt를 0 n+1개로 채운다.
• m번 반복하는 for문을 돌린다.
  -> a, b를 입력받는다.
  -> cnt[b]를 1 증가시킨다.
  -> graph[a]에 b를 넣는다.
• q를 데크로 선언한다.
• 1부터 n+1까지 반복하는 i에 대한 for문을 돌린다.
  -> 만약 cnt[i]가 0일 경우, q에 i를 넣는다.
• q가 존재하는 동안 반복하는 while문을 돌린다.
  -> q에서 cur을 추출한다.
  -> graph[cur]을 순회하는 nxt에 대한 for문을 돌린다.
  --> cnt[nxt]를 1 감소시킨다.
  --> 만약 cnt[nxt]가 0일 경우, q에 nxt를 넣는다.
  -> answer에 cur을 넣는다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> answer[i]를 공백을 두고 출력한다.

Code

from collections import deque
answer=[]
n, m=map(int, input().split())
arr=[]
graph=[[] for _ in range(n+1)]
cnt=[0 for _ in range(n+1)]
for _ in range(m):
    a, b=map(int, input().split())
    cnt[b]+=1
    graph[a].append(b)
q=deque()
for i in range(1, n+1):
    if cnt[i]==0:
        q.append(i)
while q:
    cur=q.popleft()
    for nxt in graph[cur]:
        cnt[nxt]-=1
        if cnt[nxt]==0:
            q.append(nxt)
    answer.append(cur)
for i in range(n):
    print(answer[i], end=' ')