[BOJ]11404번 : 플로이드

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

11404번: 플로이드

 

 

알고리즘 분류

• 그래프 이론
• 플로이드-와샬

 

문제 파악

 

문제의 제목처럼 플로이드-와샬 알고리즘으로 해결하는 문제이다.

 

J번째 도시에서 K번째 도시로 가는 버스 비용이 주어지며 해당 도시까지 가는 최소 비용을 구하여 출력하는 문제

1. 고려해야 될 점이 있다면 예제 입력에서 (1,2,3) , (1,2,2)처럼 출발지와 목적지가 같은데 버스 비용이 다른 경우가 있으므로 최소치가 입력되게 해줘야 하는 것

2. J번째 도시에서 K번째 도시로 가지 못한다면 0으로 처리 해줄 것!

 

import java.io.*;

public class Main {
    static final int INF = Integer.MAX_VALUE/10;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter((new OutputStreamWriter(System.out)));

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

        int[][] city = new int[N+1][N+1];

        for(int r = 1; r<=N;r++) {
            for(int c = 1; c<=N;c++)
            {
                city[r][c] = (r == c) ? 0 : INF;
            }

        }

        for(int idx =1; idx<=M;idx++)
        {
            String[] prices = br.readLine().split(" ");

            int R = Integer.parseInt(prices[0]);
            int C = Integer.parseInt(prices[1]);
            int P = Integer.parseInt(prices[2]);

            city[R][C] = Math.min(city[R][C],P);
        }

        // 경유지
        for(int i=1;i<=N;i++)
        {
            //시작점
            for(int j=1;j<=N;j++)
            {
                if(i == j) continue;
                //도착점
                for(int k = 1; k<=N;k++)
                {
                    if(j==k) continue;
                    // 시작점 => 도착점으로 가는 비용
                    // 시작점 => 도착점으로 바로 가는 비용 , 경유지를 통해 가는 비용의 합 중 최소
                    city[j][k] = Math.min(city[j][k],(city[j][i]+city[i][k]));
                }
            }
        }
        for(int r = 1;r<=N;r++)
        {
            for(int c = 1; c<=N;c++)
            {
                bw.write((city[r][c] == INF ? "0" : String.valueOf(city[r][c])) + " ");
            }
            bw.newLine();
        }
        bw.flush();
        br.close();
    }
}