[백준/16930] 플로이드 (골드 4) JAVA

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int busCount = Integer.parseInt(st.nextToken());
        int[][] city = new int[N][N];

        for (int bus = 0; bus < busCount; bus++) {
            String[] line = br.readLine().split(" ");

            int start = Integer.parseInt(line[0]) - 1;
            int end = Integer.parseInt(line[1]) - 1;
            int exp = Integer.parseInt(line[2]);
            if (city[start][end] != 0) {
                exp = Math.min(city[start][end], exp);
            }
            city[start][end] = exp;
        }

        initCity(city);
        floyd(city);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(city[i][j] + " ");
            }
            System.out.println();
        }

    }

    public static void floyd(int[][] city) {
        int N = city.length;
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (i != j) {
                        city[i][j] = Math.min(city[i][j], city[i][k] + city[k][j]);
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (city[i][j] == 10000000) {
                    city[i][j] = 0;
                }
            }
        }
    }

    public static void initCity(int[][] city) {
        int N = city.length;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (city[i][j] == 0) {
                    city[i][j] = 10000000;
                }
            }
        }
    }
}

• 플로이드 알고리즘만 안다면 쉽게 풀 수 있는 문제
• 그러나 지엽적인 함정이 존재함. edge case 확인 필요 -> N=2, bus=1인 경우 -> max값으로 설정한 10000000를 다시 0으로 바꿔야하는데 그냥 city를 모두 돌아서 체크해서 O(n^2) 감수
• max값 설정도 중요 문제의 조건에 비용은 100,000이 가능하다 했으므로 21억까지가 int한계니까 max값을 1억이나 천만정도로 여유롭게 셋팅
• Integer.maxValue 사용하면 안되는 이유는 덧셈이 들어가서 int형의 경우 max를 초과하면 +21억의 다음은 마이너스 -21억이 됨 min로직에 모두 잡혀들어가니까 쓰면 망한다.