[DFS]미로 탐색

문제

 

문제풀이

https://choi95.tistory.com/39

봉우리

해당 문제는 이전에 풀었던 봉우리 문제 풀이와 흡사하다.

 

상하좌우를 나타내는 별도의 이동 방향 배열을 선언하여 주고 현재 보드의 위치에서 해당 배열을 이용하여 상하좌우를 순회하며 갈 수 있는 길인지 아닌지 확인해주면 된다.

 

여기서 중요한 점은 봉우리 문제는 중첩 for문을 수행하여 좌표의 방향을 결정 짓었다면 이번 문제에서는 재귀 호출을 통해서 해당 요구 사항을 충족시켰다.

 

코드

function solution(board) {
  let answer = 0;
  let dx = [-1, 0, 1, 0]; //시계방향 순서대로(12시, 3시, 6시, 9시)
  let dy = [0, 1, 0, -1]; 
  let n = board.length;

  function DFS(x, y) {
    if(x === n - 1 && y === n - 1) answer++;
    else {
      for(let i = 0; i < 4; i++) {
        let nx = x + dx[i];
        let ny = y + dy[i];
        if(nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 0) { //out of range가 아니거나 현재 위치가 처음 온 위치일 경우
          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));