[백준] 11403 경로 찾기 - Graph Theory / Java

• 문제 링크

11403번: 경로 찾기

 

• 풀이 과정

모든 정점에서 모든 정점으로의 최단 거리를 구하고 정점의 개수가 1 ≤ N ≤ 100 수준이므로

플로이드 와샬 알고리즘을 활용하여 풀이한다.

 

기본적으로 거쳐가는 정점을 기준으로 최단 거리를 구하며 거쳐가는 정점이 k 일 경우

i 에서 j 로 도달하는 거리와 i 에서 k를 거쳐 k 에서 j 로 도달하는 거리는 같다는 전제를 둔다.

 

즉 k, i, j 의 3중 for문 내에서 arr[i][k] == 1 && arr[k][j] == 1 인 경우에만

arr[i][j] = 1 로 모든 정점에서 해당 정점으로 가는 경로가 있음을 표시하고,

최종적으로 해당 배열의 모든 값을 정답으로써 출력한다.

 

• 풀이 코드

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 Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		int[][] arr = new int[n][n];
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) 
				arr[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 (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");
		}
		
		bw.write(sb.toString());
		bw.flush();
	}

}