[백준][BOJ-11403][자바] 경로 찾기

www.acmicpc.net/problem/11403

11403번: 경로 찾기

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[][] map = new int[N][N];
		int[][] result = new int[N][N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[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++) {
					//중간 k를 두고 둘다 1 이면 갈 수 있다.
					if(map[i][k] ==1 && map[k][j] == 1) map[i][j] = 1;
				}
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}

정리

gooweon.tistory.com/93

플로이드 와샬(Floyd-Warshall)

플로이드 와샬을 안다면 간단하게 풀 수 있는 문제이다.

• 예제 2번을 그리면 위와 같은 형태이다.
• 방향그래프 i=2, j=3, k=7일 때를 예를 들어 보겠다.
• 2번 노드에서 3번 노드로 갈 수 있는지는 7번을 거쳐서 간다면 갈 수 있다.
• 그러면 map[i][k] == 1 이고 map[k][j] == 1 이면 해당 2 -> 3 으로 간다는 의미이다.