백준 1956 운동(Floyd-Warshall)

1956번: 운동

문제를 보면 가중치가 있는 방향 그래프에서 시작점을 따로 정하지 않고 단순히 두 마을이 사이클을 도는지 확인 하는 문제다.

 

언뜻보면 사이클이라는 단어에서 Union-Find가 생각날 수 있지만 무방향그래프일 때 사용 가능하며

방향 그래프일 때는 DFS로 자기 자신으로 돌아왔을 떄 해주면 되지만 플로이드-와샬을 이용하면 쉽게 가능

 

플로이드-와샬 후 (i,j)와 (j,i)가 INF가 아니라면 사이클이 있다는 뜻!

package practice;

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

public class Main_1956 {
    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[][] data = new int[V + 1][V + 1];

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

		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());

			data[a][b] = c;
		}

		// 플로이드 와샬 알고리즘 수행
		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 (data[i][j] > data[i][k] + data[k][j]) {
						data[i][j] = data[i][k] + data[k][j];
					}
				}
			}
		}

		int res = INF;
		for (int i = 1; i <= V; i++) {
			for (int j = 1; j <= V; j++) {
				if (i == j) 
					continue;
				
				if (data[i][j] != INF && data[j][i] != INF) {
					res = Math.min(res, data[i][j] + data[j][i]);
				}
			}
		}

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

	}

}