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

[BOJ] 백준 11657 타임머신 (JAVA)Algorithm/- Baekjoon2024. 2. 20. 14:37@Koben

Table of Contents

📑 문제

"시간이 되돌아가는 경우" -> 만약 음수 사이클이 존재한다면 무한히 시간을 되돌릴 수 있다
즉 그래프 내 음수 사이클을 판별하기 위해 벨만포드 알고리즘을 사용해야 한다!

벨만포드 알고리즘은 최단거리를 구하는 알고리즘입니다. 음수 사이클이 존재한다면 계속 최단거리가 업데이트된다는 특징이 있기 때문에

이러한 특징을 바탕으로 밸 만 포드 알고리즘 N번까지 실행했을 때 마지막까지 최단거리가 업데이트된다면

음의 사이클이 존재한다는 것을 증명할 수 있다.

위 그래프는 예제 입력 2번을 토대로 만든 그래프와 가중치이다. 밸만포드 알고리즘을 N번까지 실행해 보자

1회 차 : 1(-2) / 2(4) / 3(0)

2회 차 : 1(-4) / 2(2) / 3(-2)

3회 차 : 1(-6) / 2(0) / 3(-4)

이렇게 음의 사이클이 존재하기 때문에 각 노드가 계속 최솟값으로 업데이트되는 것을 확인할 수 있다!!

이러한 원리를 이용해서 벨만포드 알고리즘을 구현해 보자.

가장 기본적인 형태의 벨만포드 알고리즘이다. 마지막까지 업데이트된다면 음의 사이클이 존재한다는 것이고

마지막까지 실행되기 이전에 모든 노드가 업데이트되지 않았다면 음의 사이클이 존재하지 않는 것이다.

이러한 판별을 isNegative에서 true / false로 회차마다 판단한다!

벨만포드 알고리즘 입문문제로 가장 좋은 것 같다! 벨만포드를 이용해서 음의 사이클을 판단한다는 유형은 되게

신선했고, 새로운 경험이었다