[JAVA / 백준 : 1956 ] 운동

package 운동;

import java.util.*;

public class Main {

	public static final int INF = (int) 1e9;

	public static int n, m;

	public static int[][] graph;

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

		n = scan.nextInt();
		m = scan.nextInt();

		graph = new int[n + 1][n + 1];
		// 최단 거리 테이블 초기화
		for (int i = 0; i < n + 1; i++) {
			Arrays.fill(graph[i], INF);
		}

		// 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
		for (int a = 1; a <= n; a++) {
			for (int b = 1; b <= n; b++) {
				if (a == b)
					graph[a][b] = 0;
			}
		}

		for (int i = 0; i < m; i++) {
			// a에서 b로 가는 비용은 c
			int a = scan.nextInt();
			int b = scan.nextInt();
			int c = scan.nextInt();

			graph[a][b] = c;
		}
		// 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
		for (int k = 1; k <= n; k++) {
			for (int a = 1; a <= n; a++) {
				for (int b = 1; b <= n; b++) {
					graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
				}
			}
		}
		int ans = INF;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) {
					continue;
				}
				// 자기 자신을 제외한 두 정점이
				// 서로에게 가는 경로가 있다면, 사이클이 존재한다는 뜻.
				if (graph[i][j] != INF && graph[j][i] != INF) {
					ans = Math.min(ans, graph[i][j] + graph[j][i]);
				}
			}
		}

		// ans가 초기값이면 사이클이 존재하지 않음.
		ans = (ans == INF) ? -1 : ans;
		System.out.println(ans);
		scan.close();
	}
}

플로이드 와샬 문제!

 

여기서 중요한 것은, graph[i][j] 와 graph[j][i]가 INF외의 값을 갖고 있다면 사이클이 존재한 다는 것

그 사이클을 구하는 것이 중요했다.

 

 

 

 

 

 

 

 

 

 

 

 

학기 시작하니까 모든게 하기 벅차지고 그런다 ㅠㅠ 벌써 걱정