문제

입력 , 출력

solution

import sys
import collections
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
cur = [0 for i in range(n + 1)]
res = [0 for i in range(n + 1)]
dq = deque()
arr = collections.defaultdict(list)
for i in range(m):
    a, b = map(int, input().split())
    arr[a].append(b)
    res[b] += 1

for i in range(1, n + 1):
    if res[i] == 0:  #진입차수가 0 이면
        dq.append((i, 1))  #진입차수가 0 인것을 dq에 삽입
        cur[i] = 1  #1학기에 바로 이수 가능

while dq:
    a, cnt = dq.popleft()
    for i in arr[a]:
        res[i] -= 1
        if res[i] == 0:
            dq.append((i, cnt + 1))
            cur[i] = cnt + 1
print(*cur[1:])

설명

위상정렬을 이용하여 풀이를 했다.
위상정렬이란 앞에 진입하는 간선노드가 없는경우 실행을 하는 방식이다.
res에 연결된 간선노드개수를 삽입을 해주고
반복문을 통해서 진입하는 간선노드가 없는경우 큐에 삽입을 노드 번호 , 학기를 삽입을 해준다
그리고 해당 노드랑 연결되어 있는 노드들을 반복문을 사용해서 res , 간선의 개수를 1개씩 없애주고 만약에 없을경우 큐에 삽입 , 그리고 cur에 수업을 들을 수 있는 학기를 넣어준다.

후기

처음에 위상정렬에 대한 이해를 못해서 진입하는 노드의 수에 상관없이 다 실행을 해서 시간초과가 났다.
진입하는 노드가 없을경우에만 큐에 삽입을 하니 바로 풀림..