[Java] 백준 11404번. 플로이드 (#플로이드-워셜)

문항출처 : https://www.acmicpc.net/problem/11404

#플로이드-워셜
하나의 노드에서 다른 노드로 이동할 수 있는 경로를 찾는 알고리즘.
단, 다른 노드를 거쳐 간접적으로 이동할 수 있는 경로도 탐색한다.

먼저 특정 노드 i와 연결된 노드들을 찾고 노드 i와 연결된 노드 j가 있으면
노드 j로 부터 연결된 노드들을 추가로 탐색하여 노드 j와 연결된 노드k가 존재한다면,
노드 i와 노드 k의 연결성을 기록하는 방식으로 동작한다.

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

class Main {
    static class Node{
        private int index;
        private int cost;
        public Node(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }
    }

    static int n,m;
    static int[][] paths;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        paths = new int[n+1][n+1];
        //노드경로 입력받기
        while(m-->0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            if(paths[start][end] == 0 || paths[start][end] > cost){
                paths[start][end] = cost;
            }
        }
        sb = new StringBuilder();
        //노드 i와 연결된 노드 j를 찾기
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= n ; j++){
                if(i==j) continue;
                if(isConnected(i,j)){
                //노드 i, j가 연결되어있다면 j와 연결된 노드를 추가로 찾는다.
                    fw(i,j);
                }
            }
        }
        print();

    }
	
    //두 노드가 연결되어있는 판별하는 함수
    static boolean isConnected(int start, int end){
        return paths[start][end]>0 ? true : false;
    }
	
    //출력함수
    static void print(){
        for (int i = 1 ; i <=n ; i++) {
            for (int j = 1 ; j <= n ; j++) {
                sb.append(paths[i][j]+" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
	
    //노드 i와 연결된 노드 j에서부터 추가로 연결된 노드 k를 찾고
    //노드 i와 노드 k의 연결성을 기록한다.
    //그리고 노드 k로부터 연결된 노드들을 재귀적으로 찾아 노드 i와 연결한다.
    static void fw(int i, int j){
        for(int k = 1 ; k <= n ; k++){
            if(i==k) continue;
            if(isConnected(j,k)){
                int newCost = paths[i][j]+paths[j][k];
                if(paths[i][k] == 0 || paths[i][k] > newCost){
                    //노드 i와 노드 k를 연결하고
                    //노드 k에 추가적으로 연결된 노드를 탐색하여
                    //노드 i와 연결한다.
                    paths[i][k] = newCost;                    
                    fw(i,k);
                }
            }
        }
    }
}