[백준 1856번] 웜홀

난이도: 골드 III

문제 링크: https://www.acmicpc.net/problem/1865

1865번: 웜홀

백준 1865번 문제 웜홀

이 문제는 최단거리 문제인데, 노드와 노드 사이의 거리가 음수인 경우가 존재하는 특이한 경우입니다.

이를 위해 벨만-포드 (Bellman-ford) 알고리즘을 사용해야 합니다.

벨만-포드 알고리즘은 예전에 최단거리 알고리즘을 다루면서 언급한 적이 있는데,

언급만 하고 자세히 다루지는 않았습니다.

 

알고리즘에 대한 설명은 여기를 참고하였습니다.

총 노드의 개수가 n개 존재할 때, n-1번 동안 각 edge에 대해서 다음을 반복합니다.

dist[도착지] > dist[출발지] + 소요시간 인 경우, dist[도착지] = dist[출발지] + 소요시간.

이후 다시 한번 각 edge에 대해, dist[도착지] > dist[출발지] + 소요시간이라면 YES를 출력하고, 이러한 경우가 없다면 NO를 출력합니다.

 

벨만-포드 알고리즘은 문제풀이에 그렇게 자주 나오지는 않는 알고리즘인 관계로

블로그에 글은 별도로 작성하지 않으려고 합니다.

채점 결과

오타가 하나 있어서 채점을 몇 번 틀렸네요 ㅠㅠ

 

이 문제에 대해 다룬 좋은 내용의 글이 있어서 링크합니다.

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

글 읽기 - 풀이 및 논란 완전히 정리합니다.