[Algorithm] Flowd-Warshall 기법 설명 및 활용

1. Flowd-Warshall

- 변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로를 찾는 알고리즘

- 경유지를 거쳐 갈 수 있는 경우를 체크하여 기록하고 활용하는 기법

 

 

2. 예시 문제

문제)

www.acmicpc.net/problem/11403

11403번: 경로 찾기

풀이)

import java.io.*;
import java.util.*;


public class Main {
	static int N;
	static int[][] map;
	
	public static void floyd_warshall() {
		for(int k=1;k<=N;k++) {//K : 경유지
			for(int i=1;i<=N;i++) {//i : 시작점
				for(int j=1;j<=N;j++) {//j : 끝점
					if(map[i][k]==1 && map[k][j]==1)
						map[i][j] = 1;
				}
			}
		}
	}
	public static void print_map() {
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
	}
    public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	N = Integer.parseInt(br.readLine());
    	map = new int[N+1][N+1];
    	//맵 정보 입력
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=1;j<=N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	//플로이드 와샬
    	floyd_warshall();
    	
    	//출력
    	print_map();
    	
    }
}