[JAVA][백준 11657][벨만포드] 타임머신 - 컴도리돌이

반응형

---

문제에서 시작 도시 A, 도착 도시 B 그리고 버스를 타고 이동하는 데 걸리는 시간 C가 주어졌다.

여기서 중요한 부분은 이동하는 데 걸리는 시간 C가 음수인 경우도 있다는 점이다.

웬만한 그래프 문제를 풀었다면

이동 시간이 음수가 주어지면

떠올려하는 알고리즘은 하나밖에 존재하지 않는다.

벨만 포드 알고리즘

 

벨만 포드 알고리즘은 정점의 개수만큼 반복문을 돌려서

모든 간선들을 확인하여 노드 간의 최단 거리를 갱신하는 알고리즘이다.

여기서 음수 간선 순환이 발생하는지 체크하고 싶다면 

정점의 개수만큼 반복문을 돌리면 된다.

 

n번째 반복문을 돌리는데 최단 거리가 다시 갱신이 된다면 

음의 사이클이 존재하는 것이다.

---