백준 11404번 : 플로이드 java

이 문제는 플로이드-워셜 알고리즘을 푸는 문제입니다.

문제를 풀 때 주의해야하는 점은 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있다는 것입니다.

노선을 입력받아서 그 비용이 더 적은지를 비교한 후에 넣어야합니다.

플로이드 워셜 알고리즘은 각 정점으로부터 다른 정점까지 갈 때 거쳐가는 정점을 추가하면서 진행하는 알고리즘입니다.

코드를 보며 추가로 설명드리겠습니다.

---

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

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

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        int[][] map = new int[n+1][n+1];

        for(int i =0; i<=n; i++){
            for(int j = 0; j<=n; j++){
                if(i == j)
                    map[i][j] = 0;
                else
                    map[i][j] = 100_000*n;
            }
        }

        for(int i = 0; i<m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            map[a][b] = Math.min(map[a][b], c);
        }
        // 거쳐가는 지점
        for(int i = 1; i<=n; i++)
            //시작지점
            for(int j = 1; j<=n; j++)
                //도착지점
                for(int k = 1; k<=n; k++)
                    map[j][k] = Math.min(map[j][k], map[j][i] + map[i][k]);

        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=n; j++) {
                if(map[i][j] == 100_000*n)
                    System.out.print(0+" ");
                else
                    System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
}

이 문제에서는 for문 안의 시작 지점이 j이고 도착 지점이 k일 때 i를 거쳐서 가면 더 비용이 적은가를 비교하는 문제입니다.