1948 임계경로

Critical Path라고 불리는 알고리즘으로, 위상 정렬을 기반으로 시작한다

해당 알고리즘의 목적은 시작점에서 도착점으로 가는 경로가 몇개가 있는 것이 구하는 것이다

 

위상 정렬을 통해서 각 노드마다 최대로 걸리는 시간을 구할 수 있고, 다시 도착점에서 bfs를 하면서 노드의 거리가 각 노드 max 시간의 거리의 차와 같은지 비교할 수 있다

 

단, 각 노드는 여러 번 방문할 수 있다. 만일 각 도로의 길이가 모두 같은 상태라면 1은 2번을 방문해야 한다. 따라서 노드는 계속 방문하되 큐에는 한 번만 넣어주는 것이 맞다

 

 

문제: https://www.acmicpc.net/problem/1948

https://github.com/surinoel/boj/blob/master/1948.cpp