[백준] 11404번. 플로이드(JAVA)

문제

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

---

풀이(12분)

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

public class Main {


    static int n, m;
    static int[][] floyd;
    static int INF = 1_000_000_000;

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

        n = Integer.parseInt(br.readLine()); // 버스의 개수
        m = Integer.parseInt(br.readLine()); // 경로의 개수

        floyd = new int[n+1][n+1]; // 인덱스를 편리하게 사용하기 위해 +1
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j) continue; // 출발점과 도착점이 같다면 0
                floyd[i][j] = INF; // 초기화를 위한 값
            }
        }

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int fee = Integer.parseInt(st.nextToken());
            floyd[start][end] = Math.min(floyd[start][end], fee); // 여러 노선이 있을 수 있으므로 최소만 추적
        }

        floyd(); // 플로이드-와샬 알고리즘

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(floyd[i][j] == INF){
                    sb.append("0").append(" ");
                    continue;
                }
                sb.append(floyd[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);

    }

    static void floyd(){
        for(int k = 1; k<= n; k++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
            }
        }
    }


}

---

문제 풀이 전략

 

사실 문제 풀이 전략이고 뭐고 할 것이 없다. 물론 이 문제를 처음 보고 직접 시간 복잡도를 생각해내어 코드를 구현했다면 정말 좋겠지만, 이미 플로이드-와샬 알고리즘을 공부했었기에 간단하게 해결할 수 있었다.

 

플로이드-와샬 알고리즘을 모른다면 아래 링크를 참고하자.

2025.04.01 - [문제 풀이/도구정리] - [도구정리] 플로이드-와샬(Floyd-Warshall) 알고리즘

[도구정리] 플로이드-와샬(Floyd-Warshall) 알고리즘