<aside> 💛

시간제한 : 1초, 난이도 : 실버 1, 백준 : 11403번

</aside>

왜 이 문제가 플로이드-워셜과 관련이 있을까?

1. 플로이드 워셜의 핵심

• 모든 정점 쌍( i, j에 대해 어떤 정점 k를 경유했을 때 더 나은 경로가 있으면 갱신

2. 이 문제의 구조

• i에서 j로 경유지를 거쳐서라도 도달 가능한가?를 묻는 문제 → “i에서 j로 경로가 존재하는가?”를 모든 정점 쌍에 대해 확인하는 문제

i → k, k → j 모두 있으면 i → j 가 있음

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Practice62 {

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N;
	static int distance[][];
	public static void main(String[] args) throws IOException{
		N = Integer.parseInt(br.readLine());
		distance = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				int v = Integer.parseInt(st.nextToken());
				distance[i][j] = v;
			}
		}
		
		for(int k = 0; k < N; k++) {
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(distance[i][k] == 1 && distance[k][j] == 1)
						distance[i][j] = 1;
				}
			}
		}
		
		for(int i = 0 ;i < N; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print(distance[i][j] + " ");
			}
			System.out.print("\\n");
		}
	}

}

• 처음에 잘못 적은 코드