[Java] 벨만-포드 | 백준 1865 웜홀

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

 

이번 문제는 알고리즘 분류 힌트를 보고 벨만-포드 알고리즘을 추가적으로 학습한 뒤에 풀어보았다. 아직 어렵게 느껴지는 문제여서 내가 풀면서 놓치고 있었거나 새롭게 알게 된 포인트들을 간단히 정리해 보려고 한다.

 

양방향 도로 처리
처음 내 코드에서는 도로를 단방향으로만 처리하고 있었다. 도로는 양방향이기 때문에 도로를 추가할 땐, 양쪽 방향 모두 추가해야 한다.

for (int i = 0; i < m; i++) {
    edges.add(new Edge(station[i][0], station[i][1], station[i][2]));
    edges.add(new Edge(station[i][1], station[i][0], station[i][2]));
}

 

일반적인 벨만-포드에서 INF를 사용하는 이유

Arrays.fill(dist, INF);
dist[start] = 0;

• 보통 "특정 시작점으로부터의 최단 거리"를 구할 때 매우 큰 값(INF)을 dist 배열에 넣고 사용한다.
• 시작점으로부터 아직 방문하지 않은 정점들은 "도달할 수 없음"을 의미하는 INF로 표시하는데,
• 이것은 실제 경로의 길이를 구해야 할 때 필요한 방식이다.

해당 문제에서는 dist배열을 INF로 초기화 시켜주지 않고 0으로만 초기화시켜주어도 충분했다.

0으로만 초기화해도 되는 이유

Arrays.fill(dist, 0);

• 이 문제는 음의 사이클의 존재 여부만 확인하면 된다.
• 음의 사이클은 어떤 정점에서 시작해서 여러 간선을 거친 후 다시 시작점으로 돌아왔을 때, 총 거리가 음수가 되는 경우이다.
• 모든 정점을 0으로 초기화하면
  • 어떤 정점에서 시작하든 초기값이 0이다.
  • 사이클이 존재하면 그 사이클을 돌면서 거리가 계속 감소할 것이다
  • 음의 사이클이 있다면 V번째 반복에서도 거리가 갱신된다.

 

 

이 문제는 더 공부해보고 익숙해지면 다시 정리해보려한다.