[최단경로] 백준 1956번 운동(Java)

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

1956번: 운동

📚 문제

 V개의 마을과 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일반 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.

 도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.

예제 입력 1	예제 출력 1
3 4 1 2 1 3 2 1 1 3 5 2 3 2	3

 

📝 문제 해결

최단경로 사이클을 찾는 문제로 플로이드 위셜 알고리즘을 사용하여  마을 간 최단거리를 구해준다.

 

Dab = min(Dab, Dak+Dkb) 점화식을 사용하여 마을 a에서 마을b로 가는 최소 비용과 마을 a에서 마을 k를 거쳐 마을 b 로 가는 비용을 비교하여 더 작은 값으로 갱신해준다. 

(즉, 바로 이동하는 거리가 특정한 노드를 거쳐서 이동하는 거리보다 더 많은 비용을 가진다면 이를 더 짧은 것으로 갱신)

 

💻 코드

import java.util.Scanner;

public class BOJ1956 {
    public static final int INF = (int) 1e9;

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int V = sc.nextInt();
        int E = sc.nextInt();
        int[][] graph = new int[V+1][V+1];

        for(int i=1; i<=V; i++){
            for(int j=1; j<=V; j++){
                graph[i][j] = INF;
            }
        }

        for(int i=0; i<E; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph[a][b] = c;
        }

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

        int result = INF;
        for(int i=1; i<=V; i++){
            result = Math.min(graph[i][i], result);
        }

        System.out.println(result == INF ? -1 : result);

    }
}