[백준 11404] 플로이드 (플로이드 와샬 알고리즘) - 자바(JAVA)

1. 문제

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

11404번: 플로이드

 

2. 풀이

모든 정점 쌍에 대해서 A에서 B로 가는데 필요한 비용의 최솟값을 구할 때는 플로이드 와샬 알고리즘을 사용해서 구할 수 있다.

 

3. 코드

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

public class Main {

    static int N,M;
    static int[][] adj;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        M=Integer.parseInt(br.readLine());
        adj=new int[N+1][N+1];
        for(int i=0;i<M;i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int s=Integer.parseInt(st.nextToken());
            int e=Integer.parseInt(st.nextToken());
            int v=Integer.parseInt(st.nextToken());
            if(adj[s][e]==0 || adj[s][e]>v) // 값이 없거나 최소일 때
                adj[s][e]=v;
        }

        floydWarshall();

        StringBuilder sb=new StringBuilder();
        for(int i=1;i<=N;i++) {
            for(int j=1;j<=N;j++) {
                sb.append(adj[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    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(i==j||adj[i][k]==0||adj[k][j]==0)
                        continue;
                    if(adj[i][j]==0 || adj[i][k]+adj[k][j]<adj[i][j])
                        adj[i][j]=adj[i][k]+adj[k][j];
                }
            }
        }
    }
}