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

1. 문제

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

11404번: 플로이드

 

 

2. 풀이과정

문제 제목부터 플로이드 문제라고 알려주고 있었다. 플로이드 워샬로 풀면서, 이 문제에 주의할 점은 두 가지가 있다.

 

1. 같은 경로가 두 번 들어올 수 있어서, 입력받을 때 최솟값인지 확인하고 저장해줘야 한다.

2. 경로가 없는 경우는 0으로 출력해야 한다. 따라서 INF를 (도시의 개수)*(최대비용) +1 =10_000_001로 두었다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        final int INF = 10_000_001;
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int map[][] = new int[n+1][n+1];

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                map[i][j] = INF;
            }
            map[i][i] = 0;
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            map[s][e] = Math.min(map[s][e], c);
        }

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

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

 

 

결과