백준 - 14567번: 선수과목 (Prerequisite)

목차

• 문제명
• 문제풀이
• 코드

 

선수과목 (Prerequisite)

 

문제 유형 : DP, 위상정렬

난이도 : 골드 5

 

https://www.acmicpc.net/problem/14567

 

 

문제 풀이

 

위상정렬 알고리즘을 조금 응용한다.

 

큐 내부에 요소 하나를 빼내어 탐색하고 다음 탐색할 요소들을 큐에 다시 넣는 방법 대신,

 

큐에 존재하는 요소를 전부 빼내어 탐색하는 것을 하나의 loop으로 보고 모든 요소를 탐색할때까지 반복한다.

 

 

코드

 

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

N, M = map(int, input().split())

graph = [[] for _ in range(N + 1)]
degree = [0] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    degree[b] += 1

queue = deque()
result = [0] * (N + 1)

for i in range(1, N + 1):
    if degree[i] == 0:
        queue.append(i)

loop = 1
while queue:
    for i in queue:
        result[i] = loop

    size = len(queue)

    for _ in range(size):
        i = queue.popleft()
        for j in graph[i]:
            degree[j] -= 1
            if degree[j] == 0:
                queue.append(j)
    loop += 1

result.pop(0)
print(*result)

 

마무리