[Java] 백준 BOJ / 11404번: 플로이드

플로이드

문제

---

문제 설명

문제에서도 알 수 있다시피 플로이드-워셜 알고리즘을 사용하여 푸는 문제이다.

플로이드-워셜 알고리즘 은 음수 사이클이 없는 그래프 내의 각 모든 정점에서 각 모든 정점까지의 최단거리를 모두 구할 수 있는 알고리즘이다.

다익스트라 알고리즘과는 다르게 그래프에 음수 사이클만 존재하지 않으면, 음의 가중치를 갖는 간선이 존재해도 상관이 없다는 것이다.

일단 전체 코드를 보고 코드를 설명하겠다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_11404 {
    static int n, m;
    static int[][] weight;
    static int INF = 100000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        weight = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    weight[i][j] = 0;
                    continue;
                }
                weight[i][j] = INF;
            }
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            weight[start][end] = Math.min(weight[start][end], cost);
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    weight[i][j] = Math.min(weight[i][j], weight[i][k] + weight[k][j]);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (weight[i][j] != INF)
                    System.out.print(weight[i][j] + " ");
                else System.out.print(0 + " ");
            }
            System.out.println();
        }
    }
}

---

코드 설명

플로이드 워셜의 매커니즘은 간선 0개를 거친 경우, 1개를 거친 경우, ..., N개를 거친 경우의 최소 거리 비용을 비교하면서 인접행렬(각 정점에서 정점까지의 거리 비용을 나타냄)을 갱신하는 것이다.

위의 방식처럼 갱신을 하기 위해서는 주어진 비용을 토대로 어떤 정점을 거칠지 정하는 변수 하나와 모든 간선을 탐색하기 위한 변수 두개가 필요한데 해당 코드는 아래와 같다.

for (int k = 1; k <= n; k++) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			weight[i][j] = Math.min(weight[i][j], weight[i][k] + weight[k][j]);
		}
	}
}

이 코드와 같이 경유 정점을 정하는 변수 k 와 다른 모든 정점들을 탐색하기 위한 두 변수 i, j 를 사용했다.

플로이드-워셜 알고리즘을 풀 때는 처음에 모든 간선의 거리를 초기화하는 작업이 필요하다.

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		if (i == j) {
			weight[i][j] = 0;
			continue;
		}
		weight[i][j] = INF;
	}
}

여기서 INF는 처음에는 Integer.MAX_VALUE 를 사용해서 풀었는데 예제 입력을 넣어보니 아래와 같은 결과가 나왔다.

생각을 해보니 갱신하는

weight[i][j] = Math.min(weight[i][j], weight[i][k] + weight[k][j]);

이 코드에서 weight[i][k] 또는 weight[k][j] 중 하나가 INF 라면 INF + x가 음수가 되며 잘못된 결과가 나온다는 것을 생각하고 문제에서의 m의 최대 숫자인 100,000으로 설정을 했더니 예제 입출력은 맞았지만 틀렸다고 나와서 질문 게시판을 봤다.

해당 게시물에서 답을 얻을 수 있었는데 총 정점의 개수가 100개 까지 가능하기 때문에 100,000 * 100 인 10,000,000은 넘어야지 INF 변수의 역할을 할 수 있기 때문에 INF를 10,000,000 으로 초기화 해서 답을 얻을 수 있었다.