1956번 : 운동 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공 (25분)

아이디어

이 문제는 기본적으로 사이클을 만들었을때 최단거리를 구하는 문제이다.
일단 길을 전부 단 방향이고 사이클을 만들었을 때의 최단거리를 구하는 것에서 가장 쉬운 방법은

플로이드 워셜 알고리즘으로 일단 각 노드로의 최단거리를 구해둔 다음에
중첩 반복문으로 i, j를 탐색하며 i->j거리 + j->i 거리의 최소값을 구하면 그게 정답이다.

i->j로 가는 모든 경로 중 최단거리가 D[i][j]에 저장되어있고
반대로 j->i로 가는 모든 경로 중 최단 경로가 D[j][i]에 저장되어 있으니
이 둘의 합중 최소값을 출력해주면 끝.

풀이코드

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        // 입력 및 변수 선언 부분
        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 [][] W = new int [V+1][V+1];
        for(int i=0; i<= V; i++){
            Arrays.fill(W[i], Integer.MAX_VALUE);
        }
        while(E--!=0){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            W[start][end] = cost;
        }
        int [][] D;
        D = W;
        for(int k=1; k<=V; k++){
            for(int i=1; i<=V; i++){
                for(int j=1; j<=V; j++){
                    if(i==k||j==k||i==j||D[i][k]==Integer.MAX_VALUE||D[k][j]==Integer.MAX_VALUE){
                        continue;
                    }
                    D[i][j] = Math.min(D[i][j], D[i][k]+D[k][j]);
                }
            }
        }
        int result = Integer.MAX_VALUE;
        for(int i=1; i<=V; i++){
            for(int j=1; j<=V; j++){
                int cycle = D[i][j]+D[j][i];
                if(cycle>0){
                    result = Math.min(result, cycle);
                }
            }
        }
        result = result==Integer.MAX_VALUE? -1: result;
        System.out.print(result);
    }
}