플로이드 [백준 11404][JAVA][골드 4][플로이드 와샬][floydWarshall]

 

[광고 누르면 오늘의 행운 상승!!]

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

11404번: 플로이드

플로이드 와샬 문제

2차원 배열을 이용해서 i -> j 도시로 가는 최소 비용을 구한다.

i-i 나 j-j 의 경우 0을 출력한다.

i : 출발지
j : 도착지
k : 경유지 

일때, i -> k + k -> j 와 i -> j 중 작은 값이 i -> j까지의 최소 거리이다.

package Study3;

import java.io.*;
import java.util.*;
 
public class 플로이드 {
    public static int city;
    public static int[][] dis;
    public static final int INF = 1000000000;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        city = Integer.parseInt(br.readLine());
        int bus = Integer.parseInt(br.readLine());
        
        dis = new int[city][city];
        
        for(int i=0; i < city; i++) {
            for(int j=0; j < city; j++) {
                if(i == j) continue;
                dis[i][j] = INF;
            }
        }
        
        while(bus-- > 0) {
            st = new StringTokenizer(br.readLine());
            
            int A = Integer.parseInt(st.nextToken())-1;
            int B = Integer.parseInt(st.nextToken())-1;
            int D = Integer.parseInt(st.nextToken());
            
            dis[A][B] = Math.min(dis[A][B], D);    
        }
 
        floydWarshall();

        StringBuilder sb = new StringBuilder();
        for(int i=0; i < city; i++) {
            for(int j=0; j < city; j++) {
                if(dis[i][j] >= INF) sb.append("0 ");
                else sb.append(dis[i][j] + " ");
            }
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }
    
    public static void floydWarshall() {
        // 경유노드 
        for(int k = 0; k < city; k++) {
            // 출발노드
            for(int i =0 ; i < city; i++) {
                // 도착노드
                for(int j = 0; j < city; j++) {
                    //i에서 k를 거쳤다가 k에서 j 까지 가는 거리와 i에서 j 까지 가는 거리를 비교해서 작은 값이 최소거리이다.
                    dis[i][j] = Math.min(dis[i][k] + dis[k][j], dis[i][j]);
                }
            }
        }
    }
}