[BOJ] [Python] 14567 : 선수과목 (Prerequisite)

위상 정렬로 해결했다.

 

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

dp = [0] * (n + 1)

queue = []

graph = []
check = [0] * (n + 1)

result = [1] * (n + 1)

for _ in range(n + 1):
    graph.append([])

for _ in range(m):
    A, B = map(int, input().split())

    graph[A].append(B)
    check[B] += 1  # 진입 차수

    dp[B] = 1

for i in range(1, len(dp)):
    if dp[i] == 0:
        queue.append(i)

        result[i] = 1

while queue:

    num = queue.pop(0)

    if not graph[num]:
        continue

    for next_num in graph[num]:
        check[next_num] -= 1

        if check[next_num] == 0:
            result[next_num] = result[num] + 1

            queue.append(next_num)

print(*result[1:])

 

진입차수가 0일 때, 현재 노드의 순서가 결정된다.

이는 부모 노드의 순서에서 1을 더한 값이다.

 

 

주의할 점은

 

1. 과목은 1번 ~ N번까지 있다.

입력에 없지만, 범위(1~N) 안에 든다면 이 정점의 전입 차수는 0이다.

 

2. A에서 B로 간다고 했을 때, B가 없는 경우

B가 없는 경우에는 continue로 처리한다.