[Java] 백준 11403 : 경로 찾기

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

---

플로이드–워셜 문제이다. 

모든 최단 경로를 구하는 알고리즘으로, 

• 3번 중첩된 for문을 사용하기만 하면 된다.
• 3번 중첩시킬 때 유의할 점은 for문에서 가운데 노드가 가장 바깥에 있어야 한다.

 

* 배열 출력할 때 공백 있게 출력해야 한다. 

**이중 for문으로 바로바로 출력하는 것보다 StringBuilder를 사용해서 출력하는 게 더 효율적이다. 

아래가 StringBuilder 사용했을 때

 

---

import java.io.*;
public class Main {

	static int N;
	static int[][] arr;
	
	public static void main(String[] args)throws IOException{
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr= new int[N][N];
		
		for(int i=0;i<N;i++) {
			String[] str = br.readLine().split(" ");
			for(int j=0;j<N;j++) {
				arr[i][j]=Integer.parseInt(str[j]);
			}
		}
		
		 for (int k = 0; k < N; k++) { // 거쳐갈 노드
	            for (int i = 0; i < N; i++) {
	                for (int j = 0; j < N; j++) {
		        	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);
	
	}// main()
	
}// class Main