BOJ 11404 플로이드

문제 풀이 방식

노드 개수가 최대 100~200개일때 플로이드-워셜 알고리즘을 사용할 수 있다.

플로이드 워셜 알고리즘

A에서 B 노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위 K 노드가 존재한다면 이를 이루는 부분 경로 ( A -> K, K-> B) 또한 최단 경로이다.

이 원리를 동해 다음과 같은 점화식을 도출할 수 있다.

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

갈 수 있는 모든 K 노드를 탐색해 최단 경로를 계산한다.

인접 행렬을 통해 구현할 수 있다.

S, E의 값이 같은 칸(자기 자신한테 가는데 걸리는 최단 경로)은 0, 나머지는 INF로 초기화한다. 이후 이 인접 행렬에 거리 정보를 저장한다.

이후 이 점화식을 삼중 for문 형태로 반복해 리스트 값을 업데이트한다.

// 플로이드-워셜 알고리즘 
for (int k = 0; k < n; k++) { // 경유 노드 
	for (int i = 0; i < n; i++) { // 출발 노드 
		for (int j = 0; j < n; j++) { // 도착 노드 
			dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); 
		} 
	} 
}

문제 풀이 (Java)

package floyd_warshall;

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

public class b11404 {
    // 노드 개수가 최대 100~200개일때 플로이드 워셜을 사용할 수 있다.

    private static int N, M;
    private static int[][] dist;
    private static int INF = 10000000;

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

        N = Integer.parseInt(st.nextToken());
        dist = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j) dist[i][j] = 0;
                else dist[i][j] = INF;
            }
        }

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken());

            // 이동 시간에 대해 최소 입력값이 선택되도록 보장해야 한다.
            dist[a][b] = Math.min(dist[a][b], c);
        }

        floyd_warshall();

        printDist();
    }

    private static void printDist() {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (dist[i][j] == INF)
                    sb.append("0 ");
                else
                    sb.append(dist[i][j] + " ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    private static void floyd_warshall() {

        for (int k = 0; k < N; k++) { // 경유 노드
            for (int s = 0; s < N; s++) { // 출발 노드
                for (int e = 0; e < N; e++) { // 도착 노드
                    if (dist[s][k] != INF && dist[k][e] != INF) { // INF 오버플로 방지
                        dist[s][e] = Math.min(dist[s][e], dist[s][k] + dist[k][e]);
                    }
                }
            }
        }

    }
}