[JAVA] 11403. 경로 찾기

처음 입력받는 값은 각 노드의 연결 여부를 나타내는 배열을 입력받는다.

출력해야하는 결과값은 각 노드의 연결 여부를 최대한 이용하여 서로의 노드를 연결할 수 있는지 여부를 나타내는 결과값을 의미한다.

 

모든 노드의 연결 상태를 모두 확인하여 최소한의 연결 경로의 값을 찾는 플로이드 워샬 알고리즘을 이용하였다.

해당 알고리즘을 이용해 모든 연결 상태의 경우를 이용해 해당 노드들이 연결 상태인지를 알아내었다.

 

단지 최소의 값을 찾는 플로이드 워샬 알고리즘을 연결여부만을 나타내는 것으로 약간 바꾸어 연산을 하게 하였다.

최소의 값을 찾는 것이 아닌 0이면 연결이 되지 않은 상태이고, 1이면 연결 상태임을 나타내고, k를 경로로 하여 i-k와 k-j가 연결 상태이면 i-j를 연결상태로 나타내는 방식으로 연산을 진행하였다.

 

 

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B_11403_경로찾기 { 
    // 어차피 연결을 나타내는 경로찾기이므로 모든 노드를 이용해 연결이 가능한지를 찾는 알고리즘
    // 플로이드 워셜 알고리즘을 이용해 모든 경로를 통해 노드가 연결되어 있는지만 확인하면 됨.
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(in.readLine());
        int[][] arr = new int[N][N]; // 입력값이자 결과값이 될 배열
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(in.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++) {
                    // k의 노드를 거쳐서 i와 j가 연결되는지를 확인
                    if (arr[i][k] == 1 && arr[k][j] == 1) // i와 j도 k와도 연결이 되어있어야 함.
                        arr[i][j] = 1; // 서로 연결이 가능하면 연결 여부를 표시
                }
            }
        }
 
        for (int i = 0; i < N; i++) { // 연결 여부 결과를 출력함.
            for (int j = 0; j < N; j++) {
                sb.append(arr[i][j]);
                if (j != N - 1)
                    sb.append(" ");
            }
            sb.append("\n");
        }
 
        System.out.println(sb);
    }
 
}