백준 1766 Java

문제

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

알고리즘 설명

위상 정렬은 그래프의 순서를 정렬하는 알고리즘이다.
위상 정렬이 가능하려면 DAG(Directed Acyclic Graph : 방향성이 있고, 사이클이 없는 그래프)
여야 한다.

각 노드로 들어오는 간선의 갯수를 담은 INDEGREE 배열을 만들고
1. InDegree가 하나도 없는 노드들 부터 Queue에 넣어서 탐색을 한다.
2. Queue에서 뱉은 노드가 가리키는 노드의 InDegree 갯수를 차감하면서
0이 되면 Queue 에 해당 노드를 넣는다.
3. 큐가 빌때까지 계속 이 과정을 반복하면 된다.

간선에 따라서 답이 여러 개가 나올 수가 있다.
위 문제 경우에는 무조건 숫자가 낮은 것을 우선으로 출력해야 하므로
일반적인 Queue 가 아니라 PriorityQueue 를 사용했다.

구현코드

https://github.com/melong222/SW/blob/master/SW/src/BACKJOON/B1766.java