백준 11404 플로이드 Java [플로이드 워셜]

https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

주의할점

• 각 노선은 단방향이고, 여러개 존재할 수 있으므로 최소값만 담아준다
• i에서 j로 갈 수 없는 경우 0을 출력해줘야한다

100개 도시이고, 비용은 100000보다 작기 때문에 A에서 B로 가는 최대 비용은 99x100000이다

최대값은 최대비용보다 100000 더 큰 100 x 100000으로 설정해줬다 

 

플로이드 워셜 (Floyd-Warshall) 알고리즘을 알면 쉽게 풀 수 있다

플로이드 워셜 알고리즘은 도시 i에서 j까지 가는 비용이

도시 i에서 k를 경유했다 j로 가는 비용과 비교해서 최소값을 저장해나가는 알고리즘이다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.Collectors;

public class Main {
    static int[][] distance;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        distance = new int[N][N];
        for(int i = 0; i < N; i++) {
            Arrays.fill(distance[i], 100_000_000);
            distance[i][i] = 0;
        }

        for(int i = 0; i < M; i++) {
            int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            distance[arr[0]-1][arr[1]-1] = Math.min(distance[arr[0]-1][arr[1]-1], arr[2]);
        }

        floyd();
        setZero();

        for (int[] dist : distance) {
            System.out.println(Arrays.stream(dist).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
        }

    }
    static void floyd() {
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
                }
            }
        }
    }
    static void setZero() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                distance[i][j] = distance[i][j] == 100_000_000 ? 0 : distance[i][j];
            }
        }
    }
}

다음부턴 100_000_000을 상수값으로 지정해서 쓰는 연습을 해야겠다!