[Do It! 코딩테스트 자바편(김종관)] 문제 061(백준 11404번)

느낀점

• 처음에 long.MAX_VALUE로 했다가 답이 다르게 나와서 뭐지 싶었는데, 보니까 오버플로우로 답이 다르게 나왔다.
• 그래서인지 교재에서는 천만정도로 집어넣었다. 하지만 궁금해서 십만, 백만으로 집어넣은 후 돌려봤더니 둘 다 98%에서 틀렸다고 나왔다. 백만 정도면 충분히 큰 수가 아닌가? 모르겠다. 충분히 큰 수로 뭘 넣을 지 약간 감이 안 오는 문제다.

문제

오민식의 고민 (백준: 11404번)

풀이

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

public class Main {
    static int n, m;
    static long matrix[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        matrix = new long[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    matrix[i][j] = 0;
                else
                    matrix[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 1; i <= m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            if (matrix[s][e] > cost)
                matrix[s][e] = cost;
        }

        for (int k = 1; k <= n; k++) {
            for (int s = 1; s <= n; s++) {
                for (int e = 1; e <= n; e++) {
                    matrix[s][e] = Math.min(matrix[s][e], matrix[s][k] + matrix[k][e]);
                }
            }
        }
        for (int r = 1; r <= n; r++) {
            for (int c = 1; c <= n; c++) {
                if (matrix[r][c] == Integer.MAX_VALUE)
                    System.out.print("0 ");
                else
                    System.out.print(matrix[r][c] + " ");
            }
            System.out.println();
        }
    }
}