[백준] 11404번 - 플로이드 [Java]

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

 

[백준] 11404번 - 플로이드 [Java]

[백준] 11404번 - 플로이드 [Java]

---

1.  아이디어

 

제목 그대로 플로이드 워셜 알고리즘을 활용하면 되며 플로이드 워셜 알고리즘에서 사용하는 dp 테이블을 출력하면 된다.

---

2. 문제풀이

 

시작점과 도착점이 동일하면 0을 출력해야해서 dp 테이블 초기화 단계에서 0을 넣어줬고 시작점과 도착점이 동일한 경로가 여러 개 들어올 수 있어서 그 중 최솟값만 저장해야 했다.

---

3. 코드

 

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

public class Main {

    private static final int INF = 1_000_000_000;

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

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int[][] dp = new int[1 + N][1 + N];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dp[i], INF);
            dp[i][i] = 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());

            dp[A][B] = Math.min(dp[A][B], C);
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (dp[i][j] == INF) sb.append("0 ");
                else sb.append(dp[i][j]).append(" ");
            }
            sb.append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기