[BOJ/GoldIV] 11404. 플로이드 - JAVA 자바

11404번: 플로이드

• 368ms
• 플로이드 워셜 인접행렬

모든 노드에서 다른 모든 노드까지의 최단 비용을 찾는 문제로 노드의 범위(N≤100)가 작아 플로이드 워셜 알고리즘을 이용한다.

 

이 문제에서 주의해야 할 점은

• 입력값으로 중복된 출발도시와 도착도시가 들어올 수 있다는 점
• 갈 수 없는 곳은 0으로 출력해야 한다는 점

따라서 처음 입력을 받을 때, 출발노드에서 도착노드로 가는 비용이 더 작은 것을 이차원 테이블에 넣어줘야한다. 또한 모든 노드를 INF 로 초기화 후 구현하기 때문에 마지막 출력할 때, INF인 값은 0으로 바꾸어 출력해줘야 한다.

import java.io.*;
import java.util.*;

public class Main {
    static final int INF = (int) 1e9;
    static int n, m;
    static int[][] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        graph = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++)
            Arrays.fill(graph[i], INF);

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i == j) graph[i][j] = 0;

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph[a][b] = Math.min(graph[a][b], c);
        }

        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] == INF) sb.append(0);
                else  sb.append(graph[i][j]);
                sb.append(' ');
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }
}