[Java] BOJ11403_경로찾기

www.acmicpc.net/problem/11403

11403번: 경로 찾기

---

모든 정점에 대해 모든 경로를 구하는 문제로, 플로이드-와샬 알고리즘으로 구현할 수 있다.

보통의 플로이드-와샬은 최단 비용을 구하기 위해 사용되지만 이 문제 같은 경우에는 갈 수 있는지만을 판단하는 것이기 때문에 i에서 j로 가는데 k를 거쳐서 갈 수 있을 경우 arr[i][j]를 1로 업데이트해주면 해결된다.

 

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

public class Bj11403 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] arr = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < arr.length; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				//if(i==k) continue;
				for (int j = 0; j < N; j++) {
					//if(i==j || k==j) continue;
					if(arr[i][k] == 1 && arr[k][j] == 1) arr[i][j] = 1;
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		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.toString());
	}

}

 

[참고]

플로이드-와샬로 최단 경로를 구하는 대표적인 문제이므로 풀어보면 좋다.

jihunworld.tistory.com/12

[Java] BOJ11404_플로이드