2022/05/02) 4. 미로탐색 [그래프와 탐색(DFS, BFS(넓이우선))]

1. 문제

<미로탐색>
: 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성한다. 출발점은 격자의 (1,1)좌표이고, 탈출 도착점은 (7,7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다.
미로가 다음과 같다면, 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지다.
경로의 가지수를 출력하라.

2. 해결 방법

1. 문제에선 출발점을 (1,1) 도착점을 (7,7)이라고 했지만, 우린 편안하게 풀기 위해 출발점을 (0,0) 도착점을 (6,6)으로 두도록 하자. DFS는 x와 y값을 받는다.
2. 시계방향으로 탐색할 것이다. 그러므로 dx, dy배열을 생성한다. (오래전에 앞에서 배운 내용 응용)
3. for문의 변수 k를 0부터 3까지 돌리고, if문의 조건을 경계선을 넘지 않았는지 + 통로인지 확인으로 준다.
   => if(nx >= 0 && nx <= 6 && ny >= 0 && ny <= 6 && board[nx][ny] === 0){}
4. 마찬가지로 해당 인덱스의 값을 0에서 1로 바꿔주는 걸 잊지 않아야 한다.

3. 정답

   <script>
        function solution(board){  
            let answer = 0;
            let dx = [-1, 0, 1, 0];
            let dy = [0, 1, 0, -1];
            function DFS(x,y){
                if(x===6 && y===6) answer++;
                else{
                    for(let k = 0; k < 4; k ++){
                        let nx = x + dx[k];
                        let ny = y + dy[k];
                        if(nx >= 0 && nx <= 6 && ny >= 0 && ny <= 6 && board[nx][ny] === 0){ //경계선 + 조건
                            board[nx][ny]=1;
                            DFS(nx, ny);
                            board[nx][ny]=0;
                        }
                    }
                }
            }
            board[0][0]=1; //체크
            DFS(0,0); 
            return answer;
        }
        let arr=[[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]];
        console.log(solution(arr));
    </script>