[백준][Java] 11404번 플로이드 (플로이드 와샬, DP)

2가지 이유로 에러가 났는데

 

1. 경로가 같은 버스가 여러대인 경우, 버스비 계속 갱신됨

 최소 비용을 계산하기 위해서는 a도시에서 b도시로 가는 버스비 중 최소값을 배열에 넣어야하는데

a도시에서 b도시로 가는 버스가 여러대가 있는 경우도 있다는 것을 Debug로 알았고 버스비가 계속 덧씌워졌음

Math.min([기존 버스비], [새로 입력된 버스비])로 최소값 처리함

 

2. 문제의 마지막 요구 조건인 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다. 를 간과했음

 노드가 없어서 갈 수 없는 경우는 INF값으로 처리해줬는데 floyd(n)함수 돌리고 마지막에 출력하기 전에 INF값을 0으로 교체해주어야함

 

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    static int[][] Dist;
    static int INF = 100000*200;
    
    static void floyd(int n) {
        for(int k=0; k<n; k++) {
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    if(Dist[i][k]+Dist[k][j]<Dist[i][j]){
                        Dist[i][j] = Dist[i][k]+Dist[k][j];
                    }
                    
                }
            
            }
            
        }
    }
    
    public static void main(String[] args) throws IOException{
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        
        Dist = new int[n][n];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i==j) Dist[i][j]=0;
                else Dist[i][j]=INF;
            }
            
        }
        
        
        for(int i=0; i<m; i++) {
            StringTokenizer stk = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(stk.nextToken())-1;
            int b = Integer.parseInt(stk.nextToken())-1;
            int c = Integer.parseInt(stk.nextToken());
            
            Dist[a][b]=Math.min(Dist[a][b],c);
        }
        
        floyd(n);
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(Dist[i][j]==INF) Dist[i][j]=0;
            }
        }
        
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                bw.write(String.valueOf(Dist[i][j]));
                if(j<n-1) bw.write(" ");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }
}