[백준] 11403 경로찾기

문제 출처: www.acmicpc.net/problem/11403

11403번: 경로 찾기

: 가중치가 없는 방향그래프가 주어질 때 모든 정점에서의 경로가 있는지 없는지를 알아내야 한다.

: 입력값을 받고 플로이드 와샬 알고리즘과 유사한 방식으로 접근할 수 있다.

: 모든 지점을 경유지로 하여 갈 수 있는 곳들을 모두 표시한다.

: 새롭게 갈 수 있는 곳들이 반영되어 다음으로 또 갈 수 있는 곳을 알아내야 하기 때문에 map 배열에 그대로 표시해주도록 한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 경로찾기 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N;
	static int[][] map;
	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		res = 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++) {
					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++) {
				sb.append(map[i][j]).append(" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}