[BOJ] 1956. 운동 - Java

📝 문제

문제 | 백준 1956. 운동

💡 풀이 과정

⛓ 사용한 알고리즘 : 플로이드-워셜 알고리즘

문제에서 사이클의 유무를 판단하여 최단거리를 구하라고 했고, 모든 정점에서 모든 정점으로 최단거리를 계산하기 위해서는 플로이드 워셜 알고리즘을 사용하여 구할 수 있다.

사이클이 발생했는지는 a→b 가 가능하고 b→a 가 가능한 경우로 판단할 수 있다. 예를 들어 플로이드 워셜을 수행한 배열 track 이 있다고 했을 때, track[a][b]≠ INF 이고 track[b][a] ≠ INF 와 같이 두 경로가 초기값 INF가 아닌 다른 정수값을 갖고 있다면 사이클이 발생했다는 것을 의미한다.

따라서 주어진 입력을 이용해 플로이드 워셜 알고리즘을 수행한 후, 가장 짧은 거리의 사이클을 찾으면 간단하게 풀 수 있다.

코드

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

public class Main {
	
	static final int INF = 987654321;
	
	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[][] track = new int[V+1][V+1];
		
		for (int i=1;i<=V;i++) {
            for (int j=1;j<=V;j++) {
                if (i!=j) {
                	track[i][j] = INF;
                }
            }
        }
		
		
		for (int e=0; e<E; e++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
 
            track[a][b] = c;
        }//end input
		
		for(int k=1;k<=V;k++) {
			for(int i=1;i<=V;i++) {
				for(int j=1;j<=V;j++) {
					if(i==j) continue;
					
					if(track[i][j] > track[i][k]+track[k][j])
						track[i][j] = track[i][k]+track[k][j];
				}
			}
		}
		
		int ans = INF;
		for(int i=1;i<=V;i++) {
			for(int j=1;j<=V;j++) {
				if(i==j) continue;
				
				if(track[i][j]!=INF && track[j][i]!=INF)
					ans = Math.min(ans, track[i][j]+track[j][i]);
			}
		}
		
		if(ans==INF) 
			System.out.println(-1);
		else 
			System.out.println(ans);
	}
}