[Python] 백준 14567 선수과목

문제바로가기

문제 설명

• 각각의 과목은 매학기 개설되며 한 학기에 들을수있는 과목수는 제한 x
  -> 만약 선수과목이 없다면 한번에 모드과목을 수강 가능

• 각각 과목들의 선수 관계 표현-> 위상정렬 이용(defaultdict)

• 그리고 선수과목이 없는 과목들은 큐에 넣어준다(앞에 진입하는 간선노드가 없는경우 실행)

• 마지막으로 해당 노드랑 연결되어 있는 노드들을 반복문을 사용해서 res , 간선의 개수를 1개씩 없애주고 만약에 없을경우 큐에 삽입 , 그리고 cur에 수업을 들을 수 있는 학기를 넣어준다.

전체코드

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

n,m = map(int, input().split())
graph=collections.defaultdict(list)
dq=deque()
res=[0 for i in range(n+1)]
cur=[0 for i in range(n+1)]
for _ in range(m):
    x,y=map(int, input().split())
    graph[x].append(y)
    res[y]+=1
    
for i in range(1, n+1):
    if res[i]==0:
        dq.append((i,1))
        cur[i]=1
while dq:
    a, cnt=dq.popleft()
    for i in graph[a]:
        res[i]-=1
        if res[i]==0:
            dq.append((i, cnt+1))
            cur[i]=cnt+1
print(*cur[1:])