[14567] 선수과목

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

14567번: 선수과목 (Prerequisite)

위상정렬 문제다.

 

풀이

문제에서 요구하는 것은 선수과목의 순서가 아니라 각 과목을 듣기 위한 최소 학기수.

즉 위상정렬을 사용하여 큐에 몇번 접근하는지를 파악하면 된다. 

입력되는 값을 통해 각 노드의 진입차수를 저장. 진입차수가 0인 노드를 큐에 담아놓고 그래프탐색을 수행하면 된다.

그래프탐색을 통해 다른 노드로 진입시, 해당노드의 진입차수를 하나씩 차감. 0이 된다면 다음 탐색큐에 추가하면 된다.

문제의 정답을 계산하기 위해 반복문을 구분하여 탐색해야 한다. 해당 부분은 코드르 보는 게 이해하기 쉬울 것이다.

 

정답 코드