[Baekjoon 14567] 선수과목

문제

💛Ⅴ [Baekjoon 14567 - 선수과목]

문제 풀이 방법

순서가 정해져 있는 일련의 작업을 순서대로 수행해야 하기 때문에 위상 정렬 알고리즘을 이용하여 풀이할 수 있다.

1. answer 배열을 1로 초기화한다.
2. 진입차수가 0인 노드를 큐에 넣는다.
3. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣고, answer 배열의 값을 +1한다.

풀이 코드

Python

from collections import deque
import sys

input = sys.stdin.readline

v, e = map(int, input().split())
indegree = [0] * (v + 1)
graph = [[] for i in range(v + 1)]
answer = [1] * (v + 1)

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

def topology_sort():
    q = deque()

    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
                answer[i] = answer[now] + 1

topology_sort()
for x in answer[1:]:
    print(x, end=" ")