백준 1865. 웜홀

https://www.acmicpc.net/problem/1865

1865번: 웜홀

 

벨만 포드 알고리즘으로 음수 사이클이 있는지 판단하는 문제였는데 함정이 있는 문제다.

 

벨만 포드 알고리즘에서 간선들을 탐색할때 보통 시작지점이 탐색한적이 없는 정점이면 계산값을 업데이트하지 않는다.

그 이유는 벨만 포드 알고리즘은 출발점이 하나의 노드로 정해져있고 간선들을 탐색할때 간선의 시작 정점이 탐색한적이 없는 정점이라면 출발 정점에서 해당 시작 정점까지 탐색한적이 없기 때문이다. 

이렇게 해서 V-1번 간선들을 탐색하고 V번째 탐색했을때 dist가 변화가 있다면 음의 사이클이 있다고 판단하는 것이다.

 

그런데 이 문제는 출발점까지 돌아오는 음의 사이클이 있어야한다.

즉 그냥 V번쨰 탐색에서 변경되는 값이 있어야하는 것이 아니고 출발점 노드의 dist값이 변경되어야 답이 YES가 되는 것이다.

따라서 이런식으로 푼다면 모든 노드들을 출발점으로해서 벨만포드 알고리즘을 노드의 갯수만큼 돌려야한다.

그런데 이 방법으로는 시간초과가 났다. 

 

 

다시 잘 생각해보면 이 문제는 출발점이 어디인지 명시가 안되어있다.

즉 출발점이 어디든 상관없고 어쨌든 음의 사이클이 그래프에서 생기면 답이 YES 인 것이다. 

따라서 기존의 벨만 포드 알고리즘에서 간선의 시작점이 아직 탐색하지 않은 간선이면 업데이트 하지 않는다 <- 이부분을 지워준다.

위 조건은 출발점에서 나머지 다른 정점까지의 최소 비용을 탐색하기 때문에 있는 조건이다. 

 

이 문제에서는 그냥 그래프 내에 음의 사이클이 있는지만 판단하면 되기 때문에 위 조건을 없애주고, V번째 탐색에 값이 줄어드는 dist 값이 있다면 그래프 내에 음의 사이클이 있는 것이고 답은 YES가 된다. 

 

 

 

 

아래 질문글에 잘 나와있다. 

https://www.acmicpc.net/board/view/50494

글 읽기 - INF비교가 없어야 하는 이유가 뭘까요?