[BaekJoon] 백준 1956번 운동 (Java)

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

1956번: 운동

 

 

플로이드 와샬 문제이다. 

 

플로이드 와샬 알고리즘이란

모든 노드에서 모든 노드까지의 최단 거리를 구하는 알고리즘이다. 

 

3중 반복문이기 때문에 O(n^3)의 시간 복잡도를 가진다. 

 

 

이번 문제에서는

우선 노드 간에 플로이드 와샬 알고리즘 적용 후 사이클을 이루는지 확인하고 해당 최솟값을 출력하면 된다. 

 

사이클을 구성하는 지에 대한 해답은 

a - b 간의 거리를 구할때 dist[a][b], dist[b][a] 가 각자 INF 를 갖지 않으면(값을 가지고 있으면) 된다. 

 

 

코드 >> 

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

public class Main {
    static int[][] town;
    static int V;
    static int E;
    static int MIN;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
       
        V = Integer.parseInt(input[0]);
        E = Integer.parseInt(input[1]);
        town = new int[V+1][V+1];
        
        MIN = 1000000000;
        
        for(int i = 1; i<=V; i++) {
            for(int j = 1; j<=V; j++) {
                if (i == j) {
                    town[i][j] = 0;
                } else {
                    town[i][j] = 1000000000;
                }
            }
        }
        
        for(int i = 0; i<E; i++) {
            String[] road = br.readLine().split(" ");
            int a = Integer.parseInt(road[0]);
            int b = Integer.parseInt(road[1]);
            int c = Integer.parseInt(road[2]);
            
            town[a][b] = c;
        }
        
        // i = 거쳐가는 노드 , j-k 간의 거리
        for(int i = 1; i<=V; i++) {
            for(int j = 1; j<=V; j++) {
                for(int k = 1; k<=V; k++) {
                    town[j][k] = Math.min(town[j][k], town[j][i] + town[i][k]);
                }
            }
        }
        
        boolean check = false;
        
        for(int i = 1; i<=V; i++) {
            for(int j = 1; j<=V; j++) {
                if ( i != j && town[i][j] != 1000000000 && town[j][i] != 1000000000) {
                    MIN = Math.min(town[i][j] + town[j][i], MIN);
                    check = true;
                }
            }
        }
        
        
        System.out.println(check ? MIN : -1);
    }
}