[알고리즘] 플로이드 와샬 알고리즘 - 11403번 : 경로찾기(자바)

플로이드 와샬 알고리즘을 사용하는 경우는, '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶을 때 사용합니다. 이와 반대로 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘입니다.

플로이드 와샬 알고리즘 특징

핵심 아이디어는 '거쳐가는 정점' 을 기준으로 최단 거리를 구하는 것입니다. 다시 말해, i에서 j까지 가는 것과 i에서 k로 가고, k에서 j로 가는 것은 같다는 의미입니다.

각 정점이 다른 정점으로 가는 비용을 이차원 배열 형태로 출력해볼 수 있고 이 테이블이 의미하는 바는 '현재까지 계산된 최소 비용'입니다. 이차원 배열을 반복 갱신해 최종적으로 모든 최소 비용을 구해야합니다. 바로 반복의 기준이 '거쳐가는 정점' 이 됩니다.

이러한 아이디어는 i에서 j로 가는 경로가 있는지 판단할 수 있는 힌트가 됩니다.
arr[i][k]==1 이고 arr[k][j]==1인 경우만 arr[i][j]=1 로 초기화하면 됩니다.

i, j, k를 이용해 3중 for문을 작성하고 범위를 모두 0부터 n-1까지 반복해 초기화하면 정답을 찾을 수 있습니다.

코드

package simul;

import java.io.*;
import java.util.*;
/*
 * n-1개 동영상 쌍을 골라 어떤 영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다,
 * 임의의 두 쌍 사이의 동영상의 USADO를 그 경로의 모든 연결들의 USADO 중 최솟값으로 하기로 했다.
 * 
 * k값을 정해 영상과 usado가 k 이상인 모든 동영상이 추천되도록 할 것이다. 
 * 
 * 입력
 * 1- n, q
 * n-1~ 두 동영상 쌍의 USADO가 주어진다. 
 * 
 * 
 * 가중치가 없는 방향 그래프 g가 주어질 때, 모든 정점에 대해 i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램
 * 입력
 * 1- 정점의 개수 n(1<=n<=100)
 * 2~ 인접 행렬
 * 
 * i,j = 1 = i에서 j로 가는 간선이 존재한다는 뜻, i,i= 항상 0
 * 
 * 출력
 * n개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력
 * i에서 j로 가는 길이가 양수인 경로가 있으면 1로 아니면 0 출력
 */
public class BOJ_11403 {
	public static StringTokenizer st;
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StringBuilder sb = new StringBuilder();
	public static int arr[][], anw[][];
	public static void main(String[] args) throws Exception {
		int n = Integer.parseInt(br.readLine());
		
		arr = new int [n][n];
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j<n;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		
		for(int k = 0; k < n ; k++) {
			for(int i = 0; i< n;i++) {
				for(int j = 0; j<n ; j++) {
					if(arr[i][k] == 1 && arr[k][j] == 1) {
						System.out.println(i+", "+k+", "+j);
						arr[i][j] = 1;
					}
				}
			}
		}
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				sb.append(arr[i][j]+" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}

}