BOJ [선수과목]

문제 보기

한 번에 듣는 과목수에 제한이 없을 때 모든 과목을 듣는데 몇학기가 걸리는지 구하시오.

풀이

defaultdict(set)을 사용하여 각 dict에 선수과목을 set형태로 적어넣고 deque로 현재 들을 수 있는 강의를 설정한 다음 while문을 돌면서 deque에서 강의를 하나씩 빼서 들으면서 dict에 접근하여 해당 강의가 선수과목이면 제거하고 제거됐을 떄 set길이가 0이면 deque에 넣는 식으로 해결했다.

코드

from collections import deque, defaultdict

n,m = map(int,input().split())
graph = defaultdict(set)
can_take = deque([])

for _ in range(m):
	a,b = map(int,input().split())
	graph[b].add(a)

for i in range(1,n+1):
	if len(graph[i]) == 0:
		can_take.append((i,0))

answer = [[] for _ in range(n+1)]

while can_take:
	cla, day = can_take.popleft()
	answer[cla].append(day+1)
	for i in range(1,n+1):
		if cla in graph[i]:
			graph[i].remove(cla)
			if len(graph[i]) == 0:
				can_take.append((i,day+1))

for i in range(1,n+1):
	print(answer[i][0])