미로 탐색(DFS)

문제설명

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격
자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격
자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

입력 설명

• 7*7 격자판의 정보가 주어집니다.
  
  

출력 설명

• 첫 번째 줄에 경로의 가지수를 출력한다.

입력예제

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

내 코드

import java.util.Scanner;

public class Main_8_10 {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int[][] arr;
    static int cnt = 0;

    void dfs(int x, int y){
        if(x==7 && y == 7)
            cnt++;
        else{
            for(int i = 0; i < 4; i++){
                int px = x + dx[i];
                int py = y + dy[i];
                if(px >= 1 && px < arr.length && py >= 1 && py < arr.length && arr[px][py] == 0 ){
                    arr[px][py] = 1;
                    dfs(px, py);
                    arr[px][py] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main_8_10 t = new Main_8_10();
        Scanner kb = new Scanner(System.in);
        arr = new int[8][8];
        for(int i = 1; i < arr.length;i++){
            for(int j = 1; j < arr.length;j++){
                arr[i][j] = kb.nextInt();
            }
        }
        arr[1][1] = 1;
        t.dfs(1,1);
        System.out.println(cnt);

    }
}

• DFS를 활용하여 풀어보았다.
• 미로가 입력되어 있는 arr에서 출발지점을 정해주기 위해 (1,1)을 1로 초기화하였다.
• dx와 dy를 통해 현재 위치한 칸 기준 동, 서, 남, 북을 확인해 본후 0이라면 해당 칸을 1로 초기화하고 해당 칸으로 넘어간다.
• 위 방법을 반복하여 도착지점에 도착한 후 도착지점부터 다시 0으로 초기화하며 뒤로 돌아간다.
• 재귀함수를 통해 다시 뒤로 돌아가면서 0을 찾고 도착지점에 도착한다면 cnt++를 해준다.