[백준 11404] 플로이드

 

 

어려웠던 부분

• 플로이드 워셜의 인접행렬을 초기화 할 때, 도달할 수 없는 노드인 경우 INF로 채워야 하는데 INF의 범위
  • 처음에는 무조건 큰 수면 된다고 생각해서 Integer.MAX_VALUE 로 초기화 했는데, 이러면 플로이드 알고리즘에서
    maps[i][j] = Math.min(maps[i][j], maps[i][k] + maps[k][j])); 에서 Integer가 나타낼 수 있는 최댓값을 벗어나면서 음수가 되어 잘못된 결과가 나온다.
    위 문제의 경우, 최대 100개의 노드가 있으므로 다른 노드로 가는 경로가 최대 99개가 있을 수 있다. 또한, 비용은 최대 100,000 이므로 하나의 노드가 다른 노드로 갈 때 드는 최단거리를 구할 때 나올 수 있는 최댓값은 99 * 100,000 이다.
    그래서 인접행렬을 9,900,001로 채운다면 Math.min() 연산에서 문제없이 계산을 수행할 수 있다.

구현

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


public class Solution_for_11404 {
    static int N, M;
    static int[][] maps;

    static int INF = 9_900_001;

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());

        maps = new int[N][N];

        // 인접행렬을 INF로 초기화 함(시작노드와 목적지노드가 동일한 경우 0)
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i != j) {
                    maps[i][j] = INF;
                }
            }
        }
        
        // 간선을 이어줌
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());

            int startNode = Integer.parseInt(st.nextToken()) - 1;
            int endNode = Integer.parseInt(st.nextToken()) - 1;
            int cost = Integer.parseInt(st.nextToken());

            // 문제에서 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다."
            if (maps[startNode][endNode] < cost) continue;

            maps[startNode][endNode] = cost;
        }

        floyd();

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

    public static void floyd() {
        for (int k = 0; k < N; k++) {	// 중간노드
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    maps[i][j] = Math.min(maps[i][j], maps[i][k] + maps[k][j]);
                }
            }
        }
    }
}