[BOJ] 11404. 플로이드

최소 비용을 구하는 문제이다.

이 문제의 경우엔 최대 n이 100이하이고 출력시 모든 점에서 모든 점에 대한 최소비용을 출력해야함으로 가장 간단히 구현할 수 있는 플로이드와샬 알고리즘을 사용하면 된다. 플로이드와샬은 3중 for문을 이용한 알고리즘으로 만일 한점을 거친 거리가 더 가깝다면 갱신을 해주는 식으로 모든 정정들을 확인하는 알고리즘이다.

 
package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_11404_플로이드 {
    static int[][] map;
    static int INF= 987654321;
    static int N;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N=Integer.parseInt(br.readLine());
        map=new int[N][N];
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++)
                map[i][j]=INF;
        }
        
        int M=Integer.parseInt(br.readLine());
        
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int u=Integer.parseInt(st.nextToken())-1;
            int v=Integer.parseInt(st.nextToken())-1;
            int w=Integer.parseInt(st.nextToken());
            
            if(w<map[u][v])
                map[u][v]=w;
        }
        
        func();
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(map[i][j]!=INF)
                    System.out.print(map[i][j]+" ");
                else
                    System.out.print(0+" ");
            }
            System.out.println();
        }
        
    }
    
    static void func() {
        for(int k=0;k<N;k++) {
            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    if(i!=j && map[i][j]>=map[i][k]+map[k][j])
                        map[i][j]=map[i][k]+map[k][j];
                }
            }
        }
    }
}