BOJ11403 경로 찾기

https://www.acmicpc.net/problem/11403 (opens new window)

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구해야 한다.

플로이드 와샬 (Floyd Warshall) 알고리즘

다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 하지만 만약에 '모든 정점'에서 '모든 정점'으로 가는 최단 경로를 구하기 위해서는 플로이드 와샬 알고리즘을 사용해야 한다.

플로이드 와샬은 다이나믹 프로그래밍을 기반으로 한다.

제출 코드

graph 테이블은 '현재까지 계산된 최소 비용'을 기재하기 위한 용도이다. 우선 모든 값들을 INF로 채워둔다.

for (int i = 0; i < 101; i++) {
    Arrays.fill(graph[i], INF);
}

a에서 b로 가는 최소 비용과 x에서 i로 가는 비용 + i에서 y로 가는 비용 중 최소 비용을 골라 graph 테이블을 채워나간다.

for (int i = 1; i <= n; i++) {
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            graph[a][b] = Math.min(graph[a][b], graph[a][i] + graph[i][b]);
        }
    }
}

아래는 최종 제출 코드이다.

import java.util.Arrays;
import java.util.Scanner;

public class BOJ11403 {

    private static final int INF = (int) 1e9;
    private static int n;
    private static int[][] graph = new int[101][101];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        for (int i = 0; i < 101; i++) {
            Arrays.fill(graph[i], INF);
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int value = scanner.nextInt();
                if (value == 1) {
                    graph[i][j] = value;
                }
            }
        }

        // 거쳐 가기 위한 노드 i
        for (int i = 1; i <= n; i++) {
            // 출발 노드 a
            for (int a = 1; a <= n; a++) {
                // 도착 노드 b
                for (int b = 1; b <= n; b++) {
                    graph[a][b] = Math.min(graph[a][b], graph[a][i] + graph[i][b]);
                }
            }
        }

        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                if (graph[a][b] == INF) {
                    System.out.print("0 ");
                } else {
                    System.out.print("1 ");
                }
            }
            System.out.println();
        }
    }
}

References.

플로이드 와샬(Floyd Warshall) 알고리즘 (opens new window)

#algorithm #BOJ #그래프 이론 #플로이드-와샬