1956번(플로이드 워셜)

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

1956번: 운동

다익스트라 알고리즘으로 특정 정점에서 다른 특정 정점까지의 최단거리를 확인하였다. 그렇다면 모든 정점에서 모든 정점으로 가는 최단거리는 어떻게 구할까? 이때 사용하는 알고리즘이 플로이드 워셜이다. 플로이드 워셜은 모든 정점에 대해서 모든 정점으로 가는 최단거리를 중간 지점 노드를 사용하여 계산한다.

음의 간선 사이클이 존재하지 않는다면 음의 가중치를 가진 경우에도 최단 거리를 구할 수 있다는 장점이 있다.

 

동작 방식은 간단하다.

주어진 간선에 대해서 2차원 배열로 정의하고, 모든 노드에 대해서 모든 노드로 이동하는 과정에서 지나는 중간지점을 설정하여 최단거리를 계산하는 것이다.

예를 들면, 아래의 2차원 배열을 봐보자. 1에서 2로 가는 가중치가 1이고, 1에서 3으로 가는 가중치가 5이다.

2에서 3으로 가는 가중치는 2이고, 2에서 1로는 간선이 없다. 3에서 1도 간선이 없다. 3에서 2로는 가중치가 1이다.

	1	2	3
1	0	1	5
2	INF	0	2
3	INF	1	0

이 배열에서 중간에 거쳐가는 지점을 2라고 해보자.

그렇다면, 1에서 2로가는데 1의 가중치이고 2에서 3으로 가는데 2의 가중치임으로 1에서 3으로 가는 가중치는 5에서3(5->3)이된다.

1->2->3으로 이동하면서 1->3으로 이동하는 것보다 가중치가 작으니 갱신하는 것이다.

이를 반복적으로 모든 정점에 대해서 수행한다.

그러면 결과적으로 아래와 같은 결과가 나온다.

	1	2	3
1	0	1	3
2	INF	0	2
3	INF	1	0

모든 정점에 대해서 최단거리를 구하면 위의 표처럼 된다.

하지만 이 문제를 풀기 위해서는 한 단계 더 나아가야한다. 우리가 구하려는 것은 사이클이다. 즉, 자기자신으로 돌아오는 최단거리를 찾아야한다. 따라서 자기자신으로 돌아오는 가중치를 0으로 했던 것에서 무한(INF)으로 만들어서 최단거리를 구해야한다.

따라서 최단거리 표의 초기화를 아래와 같이한다. 이렇게 하면 0이 아닌 최단거리 사이클을 저장할 수 있다.

	1	2	3
1	INF	1	5
2	INF	INF	2
3	INF	1	INF

그래서 플로이드 워셜 로직을 봐보면, 아래와 같다.

public void fld_ws(){
    for(int k=1; k<=V; k++){
        for(int i=1; i<=V; i++){
            for(int j=1; j<=V; j++){
                if(dp[i][k]!=Integer.MAX_VALUE&&dp[k][j]!=Integer.MAX_VALUE){
                    dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k][j]);
                }
            }
        }
    }
    /*for(int i=0; i<=V; i++){
        for(int j=0; j<=V; j++){
            if(dp[i][j]==Integer.MAX_VALUE){
                System.out.print("INF ");
            }else System.out.print(dp[i][j]+" ");
        }
        System.out.println();
    }*/
    int min=Integer.MAX_VALUE;
    for(int i=1; i<=V; i++){
        if(min>dp[i][i]){
            min=dp[i][i];
        }
    }
    if(min==Integer.MAX_VALUE){
        System.out.println(-1);
    }
    else System.out.println(min);
}

최단거리 저장 2차원배열을 갱신하고 그중에서 자기자신으로 돌아오는 값중에 최소를 구하면된다.

 

그래서 정답 코드는 아래와 같다.

package backjoon.b1956;

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

public class b1956 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());//마을 수
        int E = Integer.parseInt(st.nextToken());//다리 수
        int[][] dp = new int[V+1][V+1];
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());//시작노드
            int b = Integer.parseInt(st.nextToken());//도착노드
            int c = Integer.parseInt(st.nextToken());//가중치
            dp[a][b]=c;
        }
        /*  1 2 3
        * 1 0 1 5
        * 2 INF 0 2
        * 3 INF 1 0
        * */

        for(int i=1; i<=V; i++){
            for(int j=1; j<=V; j++){
                if(dp[i][j]==0){
                    dp[i][j]=Integer.MAX_VALUE;
                }
            }
        }

        Graph g = new Graph(V,dp);
        g.fld_ws();
    }
}
class Graph{
    int[][] dp;
    int V;
    public Graph(int V, int[][] dp) {
        this.dp=dp;
        this.V=V;
    }
    public void fld_ws(){
        for(int k=1; k<=V; k++){
            for(int i=1; i<=V; i++){
                for(int j=1; j<=V; j++){
                    if(dp[i][k]!=Integer.MAX_VALUE&&dp[k][j]!=Integer.MAX_VALUE){
                        dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k][j]);
                    }
                }
            }
        }
        /*for(int i=0; i<=V; i++){
            for(int j=0; j<=V; j++){
                if(dp[i][j]==Integer.MAX_VALUE){
                    System.out.print("INF ");
                }else System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }*/
        int min=Integer.MAX_VALUE;
        for(int i=1; i<=V; i++){
            if(min>dp[i][i]){
                min=dp[i][i];
            }
        }
        if(min==Integer.MAX_VALUE){
            System.out.println(-1);
        }
        else System.out.println(min);
    }
}