[Algorithm] 백준 플로이드-와샬 문제 - 플로이드(11404) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 문제는 백준 플로이드-와샬(워샬) 문제 플로이드(11404) 자바 풀이를 진행하도록 하겠습니다.

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

11404번: 플로이드

 

1. 풀이 소스

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    static final int INF = 100_000_001; // 100 * 100만 범위 이므로, +1 큰 것은 넘을 수 없음
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        int m = parseInt(br.readLine());     
        int[][] graph = new int[n + 1][n + 1]; // dp 그래프를 위한 배열 초기화

        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= n; col++) {
                if (row == col) continue; // 행과 열이 같다면, 노드에서 노드로 이동하므로 0
                graph[row][col] = INF; // 출발지와 도착지가 다른 노드는 INF로 초기화
            }
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int e = parseInt(st.nextToken()); // 출발지 노드
            int v = parseInt(st.nextToken()); // 도착지 노드
            int w = parseInt(st.nextToken()); // 비용
            graph[e][v] = Math.min(graph[e][v], w); // 간선이 하나가 아닐 수 있다는 정보가 있으므로
        }

        
        for (int way = 1; way <= n; way++) { // 경유하려는 노드
            for (int row = 1; row <= n; row++) { // 출발지 노드
                if (row == way) continue; // 만약 출발지 노드와 경유하려는 노드가 같다면 패스

                for (int col = 1; col <= n; col++) { // 도착지 노드
                    // 출발지 노드와 도착지 노드가 같다면 패스
                    // 도착지 노드와 경유하려는 노드가 같다면 패스
                    if (row == col || col == way) continue;
                    graph[row][col] = Math.min(graph[row][way] + graph[way][col], graph[row][col]); // 출발 -> 경유 + 경유 -> 출발 , 출발 -> 도착 비교 
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= n; col++) {
                if (graph[row][col] == INF) sb.append(0).append(" ");
                else sb.append(graph[row][col]).append(" ");
            }
            sb.append("\n");
        }
        
        System.out.print(sb);
    }
}

 

2. 플로이드-와샬(워샬) 알고리즘 

 

플로이드-와샬 알고리즘은 그래프의 모든 노드쌍에 대한 최단 거리를 구하는 알고리즘입니다. 다익스트라 알고리즘은 한 노드에서 다른 모든 노드로의 최단 거리를 구하는 알고리즘이지만, 플로이드 와샬은 모든 노드 쌍 사이의 최단 거리를 구할 수 있습니다.

 

여기서 활용되는 원리가 DP입니다.

출발지 -> 도착지 노드로 가는 거리보다, 경유지를 들려서 가는 거리가 더 짧을수도 있습니다.

이러한 경우를 효율적으로 계산하기 위해 특정 노드에서 특정 노드로 가는 거리를 dp에 저장하고,

만약 경유지로 해당 거리를 미리 저장해놓았다면, dp 테이블에서 이를 활용하여 경유지 거리를 계산하는 것입니다.

 

dp를 활용하여, 1 -> 2까지의 거리를 저장해 놓았다면 1 -> 2 + 2 -> 3의 거리와 1 -> 3까지의 거리를 비교하여 최소 거리를 찾을 수 있습니다.

 

for (int way = 1; way <= n; way++) { // 경유하려는 노드
    for (int row = 1; row <= n; row++) { // 출발지 노드
        if (row == way) continue; // 만약 출발지 노드와 경유하려는 노드가 같다면 패스

        for (int col = 1; col <= n; col++) { // 도착지 노드
            // 출발지 노드와 도착지 노드가 같다면 패스
            // 도착지 노드와 경유하려는 노드가 같다면 패스
            if (row == col || col == way) continue;
            graph[row][col] = Math.min(graph[row][way] + graph[way][col], graph[row][col]); // 출발 -> 경유 + 경유 -> 출발 , 출발 -> 도착 비교 
        }
    }
}

 

n개의 노드를 경유하고, 각 출발지 노드 n개, 도착지 노드 n를 설정해야하므로 시간복잡도는 O(n^3)을 가지게 됩니다.

 

이상으로 백준 플로이드-와샬 문제 플로이드 풀이를 마치도록 하겠습니다.! 감사합니다.!!!