미로탐색(DFS)

 

import java.util.*;

public class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] board;
    static int answer = 0;
    
    public void DFS(int x, int y) {
        //종착점
        if(x == 7 && y == 7) answer++;
        else {
            //상하좌우로 계속 탐색해본다.
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                //경계선 안 이어야 하고 통로여야 갈 수 있음
                if(nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7 && board[nx][ny] == 0) {
                    //방문 하니까 체크
                    board[nx][ny] = 1;
                    DFS(nx, ny);
                    //다른 경로도 확인해봐야하므로 탐색한 통로를 풀어주기
                    board[nx][ny] = 0;
                }
            }
        }
    }
    

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        board = new int[8][8];
        for(int i = 1; i <= 7; i++) {
            for(int j = 1; j <= 7; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        //출발점
        board[1][1] = 1;
        T.DFS(1, 1);
        System.out.println(answer);
    }

}