[알고리즘] 위상정렬

위상정렬

위상정렬은 순서가 정해진 작업을 처리할 때, 그 순서를 정하기 위해 사용하는 알고리즘이다.
사이클이 없는 방향 그래프(DAG)에서 노드의 순서를 구할 수 있다.

물론 정렬 결과는 여러개가 될 수 있다.
생각해보면 당연하지만 주의할 점은 그래프에 사이클이 있으면 안된다는 점이다.
**DAG : Directed Acyclic Graph

알고리즘

indegree 배열과 우선순위 큐를 사용하는 방법을 알아보자.
indegree 배열 : 본인을 가리키는 화살표 수 (진입 차수)
우선순위 큐 : indegree 값이 0인 노드들을 저장

1. indegree가 0인 값들을 우선순위 큐에 넣는다.

2. 큐에서 하나를 빼고 그 수가 가리키는 수들의 indegree를 -1 해준다.
이때, indegree가 0이 되면 큐에 넣는다.
큐가 비어있을 때까지 2를 반복한다.

관련 문제

https://www.acmicpc.net/workbook/view/20205

** 그림 참고 : https://bcp0109.tistory.com/21