DFS 미로찾기

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요.

출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다.

격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

입력 

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 0

 

출력

8

 

DFS로 dx,dy배열을 순회하면서 갈수 있는 칸이면 가고 간 칸은 체크, 갔다가 돌아오면서 체크 해제 하는 방법으로 푼다

DFS 함수 내부에서는 갈수 있는 칸인지 판별하기 위해서 범위를 확인하고 넘어간다

import java.util.Scanner;

public class Main {
    static int ans = 0;
    static int[][] board;
    static int[] dx= {-1, 0, 1, 0};
    static  int[] dy = {0, 1, 0, -1};
    public void Solution(){

    }

    public void DFS(int x, int y){
        if (x == 7 && y == 7) ans++;

        else {
            for (int i =0; i < 4; i++){
                int nx = dx[i] + x;
                int ny = dy[i] + y;
                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) {
        Scanner in = new Scanner(System.in);
        Main T = new Main();

        board = new int[8][8];

        for (int i  = 1; i <= 7; i++) {
            for(int j = 1; j <= 7; j++) board[i][j] = in.nextInt();
        }

        board[1][1] = 1;
        T.DFS(1,1);
        System.out.println(ans);
    }
}