[최단 경로] 백준 11404번 플로이드(Java)

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

11404번: 플로이드

📚 문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

📝 문제 해결

간선의 가중치가 1이 아닌경우 최단경로를 찾는 문제이므로 플로이드 위셜 알고리즘을 사용하여 최솟값을 구해준다.

💡 출발 도시와 도착 도시가 같지만 비용이 다른 입력이 들어올 수 있으므로 최단 거리를 선택하여 리스트 갱신해줘야한다.

 

💻 코드

package graph;

import java.util.*;

public class BOJ11404 {

    public static final int INF = (int) 1e9;

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

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] graph = new int[n+1][n+1];

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

        for(int i=0; i<m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph[a][b] = Math.min(graph[a][b],c);
        }

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

        StringBuilder sb =new StringBuilder();
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(graph[i][j] == INF) graph[i][j]=0;

                sb.append(graph[i][j] + " ");
            }
            sb.append("\n");
        }

        System.out.print(sb);
    }
}