미로탐색(DFS)

문제

제한 사항

입출력 예

풀이

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 < dx.length; 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호출
  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));

• 미로탐색 문제이다 0일 때 지나갈 수 있으므로 지나가면서 1로 바꿔주고 끝나면 0으로 되돌려준다.
• (6,6) 좌표에 도착하면 끝까지 간 것이니 count해준다.