[Python] 백준 14567 선수과목 (Prerequisite)

14567번: 선수과목 (Prerequisite)

위상정렬 : 다이나믹 프로그래밍도 사용해야 한다. 처음 진입차수 0을 큐에 넣을때, DP값을 1로 초기화 해준다. 이건 곧바로 이수할 수 있는 과목이기때문에 1을 넣는 것이다. DP[i]값 업데이트는 이전 노드의 DP값 + 1 또는 원래 DP[i]값 중 최댓값을 택하면 된다.

 

 

전체코드

import sys
import collections

input = sys.stdin.readline

N, M = map(int, input().split())
inDegree = [0 for _ in range(N + 1)]
dp = [0 for _ in range(N + 1)]

graph = collections.defaultdict(list)
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
    inDegree[B] += 1

queue = collections.deque()
for i in range(1, N + 1):
    if inDegree[i] == 0:
        queue.append(i)
        dp[i] = 1

while queue:
    node = queue.popleft()
    for i in graph[node]:
        inDegree[i] -= 1
        dp[i] = max(dp[node] + 1, dp[i])
        if inDegree[i] == 0:
            queue.append(i)

print(*dp[1:])