풀이

보다시피 문제 이름이 플로이드이기 때문에 플로이드와샬 알고리즘을 사용하여 풀이하는 문제이다.
주의해야할 점이 몇가지 있었다.

• 다른 도시를 경유하지 않고 출발점에서 도착지로 바로 가는 노선(입력 값)이 여러 가지일 수도 있기 때문에, 입력을 받으면서 map[i][j]에 저장된 값이 0이 아닌 경우에는 입력으로 들어온 값과 이미 저장되어있던 값 중에 더 작은 값을 저장해주어야한다.
• 플로이드와샬 메서드에서 i→k 노선 or k→j 노선 중에 0인 값 즉, 노선이 없는 경우에는 연산을 진행하지 않고 넘어가야한다.
• i→k 노선 or k→j 노선이 모두 존재하는데 기존 map[i][j]값(경유하지 않고 바로 가는 경우)이 0이라면 두 값을 비교하지 않고 i → k → j 노선의 값을 저장해준다.
• 이외의 경우에는 일반 플로이드와샬처럼, 기존의 값과 k를 경유하는 값을 비교하여 더 작은 값을 저장해준다.

코드

package BOJ;

import java.io.*;
import java.util.*;

public class sol11404 {
    static int n, m;
    static int[][] map;

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

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        map = new int[n + 1][n + 1];

        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());
            if (map[start][end] != 0) {
                map[start][end] = Math.min(map[start][end], cost);
            } else {
                map[start][end] = cost;
            }
        }
        floyd();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void floyd() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (map[i][k] == 0 || map[k][j] == 0 || i == j) {
                        continue;
                    }
                    if (map[i][j] == 0) {
                        map[i][j] = map[i][k] + map[k][j];
                    } else {
                        map[i][j] = Math.min(map[i][k] + map[k][j], map[i][j]);
                    }
                }
            }
        }
    }
}