14567_선수과목 (Prerequisite)

입력

첫째 줄에 과목의 개수와 과목의 관계도 개수 입력
2번째 줄부터 M+1번째 줄까지 과목의 관계도 입력

출력

1~N까지의 과목에 대한 해당 과목을 들을 수 있는 학기 출력

조건

• 각 과목에 대한 사이클은 존재하지 않음
• 학기는 1학기가 시작

풀이

각 노드에 관해서 사이클이 존재하지 않으므로 위상 정렬로 풀이

1. indegree 확인을 위한 딕셔너리(deg)와 정답을 위한 배열(ans) 선언 후 각 과목에 대한 숫자들을 키 값으로 설정하고 각각의 value를 [다음에 들을 수 있는 과목, indegree]로 설정

deg = {}
ans = []
q = deque()

for sub in range(1, N+1):
    deg[sub] = [[], 0]
    ans.append(1)

2. M개 만큼 과목간 관계도를 입력받고 B 값으로 들어온 과목의 indegree를 +1
   이후 indegree가 0인 값들을 초기 큐에 할당

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    deg[A][0].append(B)
    deg[B][1] += 1

for key in deg.keys():
    if deg[key][1] == 0: q.append(key)

3. 큐가 empty일 때까지 반복하며 현재 참조하고 있는 과목을 수강한 이후 들을 수 있는 과목들을 모두 살펴보며 해당 과목들에 대한 indegree를 -1해주고 indegree가 0이 되는 과목들은 큐에 추가시켜주며 해당 과목을 들을 수 있는 학기를 현재 참조하고 있는 과목의 학기+1로 설정

while q:
    key_ = q.popleft()

    for elem in deg[key_][0]:
        if deg[elem][1] > 0: deg[elem][1] -= 1

        if deg[elem][1] == 0:
            q.append(elem)
            ans[elem-1] += ans[key_-1]
        else: continue

    deg[key_][0] = []

전체 코드

선수과목 (Prerequisite)