1865

오답 여부: o

편집 시간: 2022년 2월 24일 오후 3:49

코드

Algorithm/1865.py at main · Junroot/Algorithm

풀이

문제 그대로 음의 사이클이 존재하는지 확인하면 된다. 벨만 포드 알고리즘을 사용하면 음의 사이클을 확인할 수 있다.

처음에는 시작노드를 1부터 n까지 모든 경우를 다 확인해서 음의 사이클이 발생하는지 확인했는데 이는 시간초과가 발생헀다.

distances = [INF for _ in range(n + 1)] 로 시작하고, 값 갱신 조건에 distances[next] != INF 를 빼면 한번의 벨만 포드 알고리즘만으로 해결이 가능하다. 특정 위치에서 도달할 수 없는 곳에서 음의 사이클이 발생할 수도 있기 때문이다.