[백준 / BOJ] 11657 타임머신 (벨만포드)

문제

출처 : www.acmicpc.net/problem/11657

11657번: 타임머신

 

N개의 도시가 있다. 1번도시에서 출발하여 모든 도시로 갈때, 최소한의 시간으로 가는 경우를 구한다.

도시간의 시간에는 음수가 존재할수있으며, 이는 타임머신을 타고 과거로 가는경우이다.

만약 과거로 계속해서 갈수있으면 -1 을 출력하고 종료한다.

1번도시에서 해당하는 i번 도시로 갈수없다면 -1을 출력한다.

풀이

음수가중치가 존재함으로, 최단경로를 구하는 알고리즘으로 벨만포드를 사용했다.

 

기본탐색은 벨만포드를 이용하면되서 어렵지 않았으나, 음수사이클이 존재하는지 찾는게 어려웠다.

 

N의 최댓값이 500이니 1번노드부터 N번노드까지 SCC알고리즘을 사용해 사이클과 해당 사이클의 가중치합을 구해주는식의 풀이를 생각했다.

이때, 가중치의 합이 음수라면, (사이클을 반복할수록 과거로 가는것임)  -1을 출력하고 프로그램을 바로 종료해줬다.

위의 SCC를 돌렸을때 음수값을 갖는 사이클이 없다면, 벨만포드를 돌려 모든경로의 최솟값을 구해준다.

하지만, 위 처럼 풀면 시간초과가 나온다.

과거로 가는 사이클을 찾아주기 위해서, N의 최댓값에 초점을 뒀다.

N의 최댓값이 500 임으로 무한히 과거로 간다고 해도 각 노드는 최대 N번 반복된다.

-> 무한히 과거로 간다하더라도 해당 노드를 N번 초과로 반복한다면, 음수 사이클이 존재한다는 뜻이다.

visit배열을 만들어 해당 노드의 방문횟수를 저장해줬다.

 

1. 지금 가중치 값이 해당 노드에 저장된 값보다 작다면 계속해서 벨만포드를 돌려준다.

2. visit배열에 해당 노드를 반복한 횟수를 저장해준다.

3. 1 번과 2번을 반복하다, 해당노드를 N번 이상 반복했는데 벨만포드 알고리즘이 종료되지않는다면, 음수사이클이 존재한다는 뜻이다.

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/11657%20%ED%83%80%EC%9E%84%EB%A8%B8%EC%8B%A0/main.cpp

devxb/JJUNalgo