[알고리즘][DFS][11403] 경로찾기

[알고리즘][DFS][11403] 경로찾기

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

[풀이]

DFS의 기본 개념을 알고 있다면 쉽게 풀 수 있는 문제이다. 기본에 충실한 문제라서 더욱 중요하기 때문에 더욱 잘 기억해 둬야겠다고 생각한 문제이다.

1. 입력을 받은 뒤 깊이탐색을 하고 그것을 check배열에 입력한다.

2. check배열을 그대로 result배열에 넣어주면 된다.

[코드]

package algorithm_DFS;
 
import java.util.Arrays;
import java.util.Scanner;
 
 
public class q_11403 {
    static int n;
    static int[][] ans = new int[n+1][n+1];
    static int[][] arr;
    static int[] check;
    public static void dfs(int n) {
        for(int i=1;i<arr.length;i++) {
            if(arr[n][i]==1 && check[i]==0) {
                check[i] = 1;
                dfs(i);
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        //정점의 갯수 n
        n = scan.nextInt();
        arr = new int[n+1][n+1];
        ans = new int[n+1][n+1];
        check = new int[n+1];
        
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                arr[i][j]=scan.nextInt();
            }
        }
        
        for(int i=1;i<=n;i++) {
            dfs(i);
            for(int j=1;j<=n;j++) {
                ans[i][j] = check[j];
            }
            Arrays.fill(check, 0);
        }
        
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                System.out.println(ans[i][j]+" ");
            }
            System.out.println();
        }
    }
    
}