[백준 1865] 웜홀 (자바)

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

1865번: 웜홀

난이도 : 골드 4

 

음의 가중치가 있는 그래프의 최단 거리를 구할 수 있는 벨만-포드 알고리즘을 이용했습니다.

다익스트라 알고리즘은 음의 가중치를 가지는 그래프의 최단 경로를 구하지 못하고 무한 루프에 빠지게 됩니다.

하지만 벨만-포드 알고리즘은 최단 경로를 구할 수 있고 엄청난 시간 복잡도를 자랑합니다.

또, 음의 가중치들이 만드는 사이클을 탐지할 수 있습니다.

 

벨만-포드 알고리즘은 모든 간선을 V-1번 검사합니다. 이 과정에서 점점 최적화를 해나갑니다.

다익스트라는 각 정점을 지날 때 그 정점에 연결된 간선들을 한번씩 검사하는 반면에 벨만-포드 알고리즘은 모든 간선을 V-1번 검사합니다.

그리고 이 그래프가 사이클을 가지는지 확인하기 위해 1번 더 검사하여 총 V번 모든 간선의 개수를 검사합니다.

https://bluemoon-1st.tistory.com/17

벨만-포드 알고리즘(Bellman-Ford)

왜 다익스트라와는 다르게 모든 간선을 V번 검사하는지 이해가 되지 않았지만, 이 블로그의 글을 보고 이해했습니다.

다익스트라는 최적 가중치를 정점마다 구할 수 있었지만, 벨만-포드 알고리즘은 점점 최적화를 해나가는 것을 볼 수 있습니다. 특히 음의 가중치를 계산한 전과 후를 비교하면 이해가 될 듯합니다.

 

시간 복잡도는 정점의 개수 V, 간선의 개수 E라고 한다면 O(VE)입니다.

 

모든 정점에 대해 V-1번 검사합니다. 그 후 1번 더 검사했을 때 최적 거리를 저장하는 dist배열에 변화가 있다면 음의 사이클이 존재하는 것으로 판단합니다.

---

전역 변수

int n = 정점의 개수
LinkedList<Edge> list[] = 연결 정보를 저장하는 리스트

함수

void main

입력을 받고 연결 정보를 받아 저장합니다. 문제에서 출발점이 정해지지 않았으므로 1~n까지를 출발점으로 하여 사이클의 상태를 확인합니다. 만약 1번이라도 사이클이 존재한다면 YES를 sb에 달아주고 사이클이 모두 존재하지 않는다면 NO를 달아줍니다.

(bellmanFord 호출)

 

boolean bellmanFord

정점까지의 거리를 저장하는 dist배열을 선언하고 INF(987654321)로 채워줍니다.

시작점의 값을 0으로 맞춰주고 n-1번 모든 간선을 검사합니다. 만약 update가 되지 않는다면 더 이상 진행해도 값의 변화가 없으므로 break 해줍니다.

n-1번째 검사에서 update가 됐다면 사이클 검사를 해줍니다. 만약 이 검사에서도 값이 변한다면 사이클이 있는 것이므로 true를 반환합니다.

그렇지 않다면 false를 반환합니다.

 

class Edge

간선의 정보를 저장합니다. 목적지 v와 이 간선의 가중치 w가 있습니다.