[Javascript] 미로탐색

[인프런] 자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비) - 미로탐색

내 코드

function solution(board) {
  let answer = 0;
  let visited = Array.from(Array(7), () => Array(7));
  let dx = [0, 0, -1, 1];
  let dy = [-1, 1, 0, 0];
  function DFS(x, y) {
    if (x === 6 && y === 6) {
      answer++;
      return;
    }
    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx < 0 || nx >= 7 || ny < 0 || ny >= 7) {
        continue;
      }
      if (!visited[nx][ny] && board[nx][ny] === 0) {
        visited[nx][ny] = true;
        DFS(nx, ny);
        visited[nx][ny] = false;
      }
    }
  }
  visited[0][0] = 1;
  DFS(0, 0);
  return answer;
}

강사님 코드와 차이점

나는 2차원 배열 visited를 추가로 선언했다.

강사님은 기존에 있는 board 배열의 값을 1로 바꾸는 방법을 사용했다.

이렇게 하면 메모리를 더 절약할 수 있을 것 같다.

 

개선한 코드

function solution(board) {
  let answer = 0;
  let dx = [0, 0, -1, 1];
  let dy = [-1, 1, 0, 0];
  function DFS(x, y) {
    if (x === 6 && y === 6) {
      answer++;
      return;
    }
    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx < 0 || nx >= 7 || ny < 0 || ny >= 7) {
        continue;
      }
      if (board[nx][ny] === 0) {
        board[nx][ny] = 1;
        DFS(nx, ny);
        board[nx][ny] = 0;
      }
    }
  }
  board[0][0] = 1;
  DFS(0, 0);
  return answer;
}