[백준] 11404번 플로이드

🔔 문제

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

🎯 풀이방법

Floyd Warshall 알고리즘

모든 정점에서 모든 정점으로의 최단경로를 구하고 싶다면 플로이드 워셜 알고리즘을 사용해야 한다. 특징에는 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다.

예를들어, 노드 k를 거쳐가는 경우에, X에서 Y로 가는 최소 비용과 X에서 노드 k로 가능 비용+노드 k에서 Y로 가는 비용 중 최소 비용을 계산한다. 그러므로 점화식은 다음과 같다.

if d[출발][경유]+d[경유][도착] < d[출발][도착]
	d[출발][도착] = d[출발][경유]+d[경유][도착]

pseudo-code

1. 거리배열을 무한대(INF)로 초기화

2. 시작도시, 도착도시, 간선 비용 입력 받는다. 단, 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있기 때문에 입력받을 때 비용이 기존비용보다 작으면 갱신한다.

3. 플로이드-워셜 알고리즘 수행한다. 3중 for문을 수행 (경유→출발→도착)

4. 거리배열을 출력한다. 이때 시작 도시와 도착 도시가 같거나 비용이 무한대(INF)이면 0을 출력한다.
   
   

💡 이 문제를 통해 얻어갈것

플로이드-워셜 알고리즘을 사용한 최단 경로 구하는 문제

💻 Java code

메모리 43584KB, 시간 468ms

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

// 플로이드 - 와샬 알고리즘 : 모든 정점에서 모든 정점으로의 최단경로
// 시간복잡도 O(n^3)
public class Main {
    static int INF = Integer.MAX_VALUE;
    static int N,M;
    static long[][] d;

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

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        // 초기화
        d = new long[N+1][N+1];
        init();

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()); // 시작 정점
            int b = Integer.parseInt(st.nextToken()); // 도착 정점
            int c = Integer.parseInt(st.nextToken()); // 비용

            // 만약 값이 이미 입력됬다면 비교
            if(d[a][b] > c) {
                d[a][b] = c;
            }
        }

        floydWarshall();

        // 배열 출력
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(i==j || d[i][j] == INF)
                    sb.append(0 + " ");
                else
                    sb.append(d[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }

    private static void init() {
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                d[i][j] = INF;
            }
        }
    }

    private static void floydWarshall() {
        for(int k=1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if(d[i][k] + d[k][j] < d[i][j])
                        d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}