14567 선수과목 (Prerequisite)

선/후수과목 관계가 주어졌을 때 모두 수강하려면 얼마나 걸릴지 구하는 문제

---

선수과목에서 후수과목으로 가는 간선을 가지는 그래프를 떠올려보자.

1. 이 그래프는 DAG이다.
2. 이 그래프에서 진입차수가 0인 정점은 선수과목이 없는 과목이므로 바로 수강 가능하다.

진입차수가 0인 과목을 큐에 넣고 순회한다. 한 과목을 순회할 때마다 후수과목의 진입차수를 1씩 뺀다. 이때 진입차수가 0이 되면 큐에 넣는다. 모든 정점을 방문할 때까지 즉, 큐가 빌 때까지 반복하여 정답을 구할 수 있다.

N, M = map(int, input().split())
adj = [[] for i in range(N)]
ind = [0] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    ind[b] += 1
    adj[a].append(b)

from collections import deque
q = deque()
for i in range(N):
    if ind[i] == 0:
        q.append(i)

result = [0] * N
order = 0
while len(q):
    l = len(q)
    for i in range(l):
        e = q.popleft()
        result[e] = order
        for nxt in adj[e]:
            ind[nxt] -= 1
            if ind[nxt] == 0:
                q.append(nxt)
    order += 1

print(' '.join([f'{e + 1}' for e in result]))

추가로 문제에서 선수과목이 후수과목보다 항상 앞선 번호로 주어진다고 했으므로 큐 없이 앞에서부터 진입차수 + 1으로 후수과목들의 진입차수를 갱신하면 된다.

N, M = map(int, input().split())
adj = [[] for i in range(N)]
ind = [0] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    ind[b] += 1
    adj[a].append(b)

result = [0] * N

for i in range(N):
    for v in adj[i]:
        result[v] = max(result[v], result[i] + 1)

print(' '.join([f'{e + 1}' for e in result]))