11404번(플로이드 워셜)

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

11404번: 플로이드

이 문제도 운동(1956)문제와 같은 플로이드 워셜을 이용한 문제이다.

로직은 1956과 거의 똑같기 때문에 간단하게 동작 방식만을 설명하자면, 시작 지점과 도착 지점 사이의 중간지점 즉, 거쳐가는 지점이 있다고 가정하고, 최단거리를 구하는 것이다. 다익스트라가 특정 정점에서 특정 정점으로 가는 최단거리였다면 그걸 전체 정점에서 전체 정점으로 가는 최단거리라고 생각하면 된다.

정답 코드는 아래와 같다.

package backjoon.b11404;

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

public class b11404 {
    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[][] city = new int[N+1][N+1];

        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());
            if(city[a][b]!=0){
                city[a][b]=Math.min(city[a][b],c);
            }
            else city[a][b]=c;
        }
        Graph g = new Graph(N,city);
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(i!=j && g.city[i][j]==0){
                    city[i][j]=Integer.MAX_VALUE;
                }
            }
        }
        g.fld_ws();
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(g.city[i][j]==Integer.MAX_VALUE){
                    sb.append(0).append(" ");
                }else sb.append(g.city[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}
class Graph{
    int[][] city;
    int N;
    public Graph(int N, int[][] city){
        this.city=city;
        this.N=N;
    }
    public void fld_ws(){
        for(int k=1; k<=N; k++){
            for(int i=1; i<=N; i++){
                for(int j=1; j<=N; j++){
                    if(city[i][k]!=Integer.MAX_VALUE && city[k][j]!=Integer.MAX_VALUE){
                        city[i][j]=Math.min(city[i][j],city[i][k]+city[k][j]);
                    }
                }
            }
        }
    }
}

플로이드 워셜에 대한 설명은 아래의 글을 참고하면 좋겠다.

https://parkjunbackend.tistory.com/83

1956번(플로이드 워셜)