미로탐색

미로 탐색

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

틀린 구현 코드

코드를 ide에서 따로 저장안하고 바로 고쳐버려서 코드는 없지만
문제점은 다음과 같았음.

1. 방향을 돌아가면서 바꿔야하는 아이디어는 알았는데 방향을 잘못 설정해주었음. 만약 좌표가 (1,1)에서 시작하면 (row+1,col), (row,col+1), (row+1,col+1) 이렇게만 진행. 방향이 4방향이 아님.
2. 쓸데 없는 배열 선언. 지났는지 여부를 판단하기위해 check이라는 이차원 배열을 선언해주었는데 board자체에서 검사해주면 됨.

모범답안 참고 후 구현 코드

public class 미로탐색_DFS {
    final static int N = 7;
    static int answer = 0;//도착지까지 갈 수 있는 방법의 수
    static int[][] board = new int[N+1][N+1];
    static int[] dir_x = {-1,0,1,0};
    static int[] dir_y = {0,1,0,-1}; //6시 -> 3시 -> 12시 ->9시 방향

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

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

        board[1][1] = 1;
        dfs(1,1);

        System.out.println(answer);
    }

    static void dfs(int row,int col){
        if(row==N && col ==N){
            answer++;
            return;
        }
        else{
            //방향보면서 뻗어나가야함
            for(int i=0;i<4;i++){
                int nx = row+dir_x[i];
                int ny = col+dir_y[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;
                }
            }
        }
    }

}

방향 dx, dy를 각각 선언하고 방향 4개에 대해서 for문을 돌면서 dfs호출. 이때 조건은 8x8로 선언한 보드사이즈(1~7까지로 하기 위해)를 안넘고, 값이 0인 위치에 대해서만 넘어가도록.

어제 본 코딩테스트 마지막 문제가 이 문제랑 비슷하게 dfs써서 푸는 문제였는데 조건을 잘못 걸었는지 테스트케이스 몇개만 맞고 오답처리됐었다... ㅠ..
dfs문제는 조건이랑 백트래킹 해주는게 중요한 것 같다.