[24526] 전화 돌리기

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

24526번: 전화 돌리기

위상정렬 문제다.

 

풀이

사이클이 생기는 노드, 그리고 해당 노드로 진입하는 노드를 제외한 나머지 노드의 수를 출력하는 문제다. 

주어지는 간선의 방향을 반대로 저장하고 위상정렬을 통해 탐색한다면, 정답을 구할 수 있다. 이유는 위상정렬의 필수조건인 indegree가 0인 노드를 큐에 담아 탐색하는 부분에서 찾을 수 있다. 사이클이 발생한다는 것은 곧 indegree가 0이 되지 않는다는 이야기이기에 역방향으로 탐색하게 되면 사이클은 큐에 담기지 않게 된다.

 

예제의 경우를 그래프로 그려보면 좌측과 같다. 위상정렬을 통해 탐색을 시작하면 1부터 시작하기에 처음부터 사이클이 일어날지 알 수 없다. 반면 우측의 경우처럼 역방향으로 그래프를 그리면 4와 6만 큐에 담긴 채 사이클이 일어나는 3번 노드는 큐에 담기지 않게 되고 그대로 탐색이 종료된다. 따라서 정답은 4, 6번 학생인 두 명의 부원이라는 정답을 출력할 수 있다.

 

정답 코드