[백준]11404: 플로이드 - JAVA

[백준]11404: 플로이드 

www.acmicpc.net/problem/11404

11404번: 플로이드

풀이

최단거리 알고리즘 공부한 기념으로 관련 문제들을 풀어보았다.

 

이 문제는 플로이드-워샬 알고리즘을 쓰면 바로 답이 나온다! 모든 정점에서 모든 정점까지의 최단거리를 구하는 문제이다.

 

문제를 꼭 제대로 읽자! 출력 설명에 i에서 j로 가는 길이 없으면 0을 출력한다고 되어있다. 이를 체크 안해주면 98프로에서 틀린다. 꼭꼭 문제를 제대로 읽자.

 

코드

import java.util.*;
 
public class Main {    
    
    static int[][] node;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int m = scan.nextInt();
        
        node = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                node[i][j] = 100000001;
            }
            node[i][i] = 0;
        }
        
        for(int i = 0; i < m; i++) {
            int start = scan.nextInt();
            int end = scan.nextInt();
            int cost = scan.nextInt();
            if(node[start][end] > cost) node[start][end] = cost;
        }
        
        //플로이드-워샬
        for(int k = 1; k < n + 1; k++) {
            for(int i = 1; i < n + 1; i++) {
                for(int j = 1; j < n + 1; j++) {
                    if(node[i][j] > node[i][k] + node[k][j])
                        node[i][j] = node[i][k] + node[k][j];
                }
            }
        }
        
        for(int i = 1; i < n + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                if(node[i][j] == 100000001) System.out.print("0 "); //i -> j로 갈 수 없는 경우 0출력
                else System.out.print(node[i][j] + " ");
            }
            System.out.println();
        }
    }
}