침투 - 13565

문제

풀이

import java.util.Scanner;

// 침투 - DFS - s2
public class ex13565 {
    static int n,m;
    static int board[][];
    static int[] dx={0,1,0,-1};
    static int[] dy={1,0,-1,0};
    static boolean flag;

    public static void DFS(int x,int y){
        if(x==n-1){
            flag=true;
            return;
        }
        board[x][y]=2;
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<m && board[nx][ny]==0){
                DFS(nx,ny);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        board = new int[n][m];
        for (int i=0; i<n; i++) {
            String temp = sc.next();
            for (int j=0; j<m; j++) {
                board[i][j]=temp.charAt(j)-'0';
            }
        }

        for(int i=0; i<m; i++){
            if(flag==true) break;
            if(board[0][i]==0){
                DFS(0,i);
            }
        }

        if(flag==true) System.out.println("YES");
        else System.out.println("NO");

    }
}

위에서 아래로 전류를 흘려보내야한다. 0으로 입력된곳이 전류가 흐를 수 있다. 1행을 훑으면서 DFS()를 호출해주고 4방향으로 다음좌표로 DFS()를 재귀호출한다. 지나온길은 다시 돌아가지 않기 위해서 임의로 2로 바꿔준다. 이런식으로 진행하다가 재귀가 마지막행에 도착했을 때 flag를 참으로 상태를 변경해주고 바로 return시킨다. 그렇게 DFS()를 끝내고 결과를 출력한다.!! 기본적인 DFS문제이다.