[Algorithm] 위상 정렬(Topology Sort)

a보다 b가 먼저 실행되어야해!

 

어떤 일을 하는 순서를 찾는 알고리즘이다.
즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

 

[알고리즘 구현하기]

1. 각 노드들의 진입 차수 계산
2. 진입 차수가 0(들어오는 간선의 수가 0)인 노드들을 큐에 삽입
3. 큐에서 노드를 꺼내 연결된 간선을 제거
4. 제거로 인해 진입 차수가 0이 된 노드를 큐에 삽입
5. (3)~(4) 번을 반복하며 큐가 비었으면 종료

https://www.acmicpc.net/problem/1766 백준 문제집 문제를 푸는데 자꾸 시간초과가 났다 ㅠㅠ 3이랑 4 과정을 for문 하나에서 해결해야 했는데 그게 문제였던 것 같다....

 

 

최단거리 구하기

각 노드에 저장소를 만들어서 min거리를 저장해두는 방식으로 해결한다. 

 

[참고]
https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

https://ssungkang.tistory.com/entry/Algorithm-위상정렬