[백준 / BOJ] 11657 타임머신 (SPFA)

문제

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

11657번: 타임머신

 

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

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

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

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

 

풀이

벨만포드 풀이 : dlwnsdud205.tistory.com/8

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

벨만포드는 모든간선에대해 업데이트를 해주지만, SPFA알고리즘은 변경된값들에 대해서 업데이트를 해준다.

벨만포드로 한번 풀었던 문제라 쉽게 풀수있었다.

deque 배열을 만든다(변경된 노드들을 받아줌)

 

알고리즘 동작과정

 

1. deque의 가장앞 인덱스를 pop하고 이 인덱스와 인접한 노드를 봐준다. 인접노드들을 최솟값으로 변경할수있다면 변경하고 deque에 넣어준다.

단, 이때 이미 덱에 해당 노드가 들어가있다면 집어넣지 않는다.

위 과정을 반복하면된다.

 

음수사이클을 찾는과정은 벨만포드 풀이와 마찬가지로 한 인덱스를 N번 초과로 반복하면 음수사이클이 존재하는것으로 -1을 출력하고 종료한다.

 

걸린시간은 SPFA가 4배더 짧았다

벨만포드 : 32ms

SPFA : 8ms

 

소스코드

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

devxb/JJUNalgo