[BOJ][Java] 11403번 경로 찾기

문제 설명

문제 링크 : https://www.acmicpc.net/problem/11403

 

특정 정점에서 각 정점까지 연결이 되어있는지를 물어보는 문제이다.

플로이드 워셜 알고리즘을 이용하면 되는데 여기서 이 문제는 최단거리를 물어보는 문제가 아니기 때문에 

이 문제와는 다르게 최단거리를 업데이트해주는 부분만 변형해 주면 된다.

 

플로이드 워셜이 S부터 E까지의 최단 거리는 S와 E 사이에 있는 K 정점을 기준으로 S -> K + K -> E까지의 거리가 

기존의 S -> E 까지의 거리보다 가깝다면 업데이트를 해주는 방식이었다.

 

이 문제에서는 S -> K 까지 연결되어 있고 K -> E까지 연결되어 있다면 S -> E는 연결되어 있다는 로직으로

수정해 주면 된다.

 

package boj;

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

public class BOJ11403 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N+1][N+1];

        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int k = 1; k <= N; k++){
            for(int s = 1; s <= N; s++){
                for(int e = 1; e <= N; e++){
                    if(arr[s][k] > 0 && arr[k][e] > 0) arr[s][e] = 1;
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                sb.append(arr[i][j]).append(" ");
            }
            if(i != N){
                sb.append("\n");
            }
        }

        System.out.println(sb);
    }
}