/ BOJ

BOJ_11404_플로이드_JAVA

문제 : 플로이드

링크 : BOJ_11404_플로이드

접근 방식

제목부터 플루이드 워샬 문제라는 것이 보일 정도로 명확하게 플루이드 워샬 문제이다.

이번 문제에서 주의해야할 점은, 연결되지 않은 곳은 0으로 만들어야하기 때문에 처음에 플루이드 워샬을 돌리기 위해 INF로 처리해두었던 값들을 출력 전에 0으로 다시 바꿔야 하는 것이다.

그리고, 이전의 케빈 베이컨 문제와 달리 가중치가 있고 무방향이 아니므로 이 부분도 생각해야한다.

앞서 적은 2가지만 주의하면 어렵지 않게 풀 수 있는 문제라고 생각한다.

소스 코드

import java.util.Scanner;

public class BOJ_11404_플로이드 {

	static final int INF = 9999999;
	static int N, adjMatrix[][], M;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();

		adjMatrix = new int[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				adjMatrix[i][j] = INF;
				if (i == j) {
					adjMatrix[i][j] = 0;
				}
			}
		}

		for (int i = 0; i < M; ++i) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			adjMatrix[a][b] = Math.min(adjMatrix[a][b], c);
		}

		for (int k = 1; k <= N; ++k) {
			for (int i = 1; i <= N; ++i) {
				if (i == k)
					continue;
				for (int j = 1; j <= N; ++j) {
					if (i == j || k == j)
						continue;
					if (adjMatrix[i][j] > adjMatrix[i][k] + adjMatrix[k][j]) {
						adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
					}
				}
			}
		}


		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if(adjMatrix[i][j] == INF) {
					adjMatrix[i][j] = 0;
				}
				System.out.print(adjMatrix[i][j] + " ");
			}
			System.out.println();
		}

	}

}