플로이드 워셜 백준 11404 (JAVA)

서론

 

Floyd Warshall 알고리즘은 최단 경로를 구하는 방법중 하나이다.

 

동적계획법으로 접근하는데 시간 복잡도는 O(N^3)이다.

 

최단경로 구하는 알고리즘인 dijkstra와 비교하자면

 

간선 수가 많으면 Floyd 가 빠를 수 있다.

 

시작 정점이 정해져 있으면 dijkstra가 당연히 빠르다.

 

음의 가중치가 존재한다면 dijkstra는 사용할 수 없지면 Floyd는 사용가능하다.

구현 코드

 

for i in vertex // 경유
    for j in vertex //시작점
        if i == j continue
        for k in vertex  //도착점
            if i == j or j==k continue
                arr[j][k] = min(arr[j][i] + arr[i][k] , arr[j][k])

 

문제에 적용

 

문제 : https://www.acmicpc.net/problem/11404

11404번: 플로이드

알고리즘

1. 문제 그대로 플로이드 알고리즘을 사용하면 된다.

 

2. 못가는 경우 가중치를 MAX_integer로 할 경우 발생하는 overflower에 조심해야한다.

구현코드

 

public class Main_11404 {
    static int mat[][];
    static final int max = 1000000000;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer s;
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(in.readLine().trim());//
        int m = Integer.parseInt(in.readLine().trim());
        mat = new int[n+1][n+1];
        for (int i = 0; i < m; i++) {
            s = new StringTokenizer(in.readLine()," ");
            int a =Integer.parseInt(s.nextToken());
            int f = Integer.parseInt(s.nextToken());
            int v = Integer.parseInt(s.nextToken());
            if(mat[a][f] == 0)
                mat[a][f] = v;
            else
                mat[a][f]=Math.min(mat[a][f], v);
        }

        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if(mat[i][j] == 0)
                    mat[i][j] = max;
            }
        }

        for (int i = 1; i < n+1; i++) { //경유
            for (int j = 1; j < n+1; j++) { // 시작
                if(i == j)
                    continue;
                for (int j2 = 1; j2 < n+1; j2++) { //도착
                    if(i == j2 || j==j2)
                        continue;
                    if(mat[j][i]+mat[i][j2] < mat[j][j2])
                        mat[j][j2] = mat[j][i]+mat[i][j2];
                }
            }
        }


        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if(mat[i][j] == max)
                    sb.append("0 ");
                else
                    sb.append(mat[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());

    }
}