[백준 11403] 경로 찾기

 

이차원 배열을 짜서 DFS 를 수행하면 된다.

 

노드에 간선이 있을 경우 노드를 계속 타고 들어가며 방문한 노드 배열 정보를 1로 표시한다.

 

 

public class Main {

    static int n;
    static int a[][];
    static int path[][];
    static boolean visited[];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        a = new int[n+1][n+1];
        path = new int[n+1][n+1];
        visited = new boolean[n+1];
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        for(int i=1; i<=n; i++) {
            dfs(i);
            for(int j=1; j<=n; j++) {
                if(visited[j])
                    path[i][j] = 1;
            }
            Arrays.fill(visited, false);
        }
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                System.out.print(path[i][j] + " ");
            }
            System.out.println();
        }
        sc.close();
    }
    
    public static void dfs(int x) {
        for(int i=1; i<=n; i++) {
            if(!visited[i] && a[x][i] == 1) {
                visited[i] = true;
                dfs(i);
            }
        }
    }
}