미로 탐색 : DFS

내 풀이

function solution(board) {
  let answer = 0;
  let check_table = Array.from({ length: 8 }, () => Array.from({ length: 8 }, () => false));

  const d = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1]
  ];

  function DFS(x, y) {
    if (check_table[x][y] === true) return;
    if (arr[x][y] === 1) return;
    if (x === 6 && y === 6) {
      answer++;
      return;
    }
    for (let [dx, dy] of d) {
      nx = x + dx;
      ny = y + dy;
      if (0 <= nx && nx <= 6 && 0 <= ny && ny <= 6) {
        check_table[x][y] = true;
        DFS(x + dx, y + dy);
        check_table[x][y] = false;
      }
    }
  }
  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]
];

[0, 0]은 check를 안해주었는데 왜 답이 나오는지 모르겠다;

내 풀이 수정

function solution(board) {
  let answer = 0;
  let check_table = Array.from({ length: 8 }, () => Array.from({ length: 8 }, () => false));

  const d = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1]
  ];

  function DFS(x, y) {
    if (check_table[x][y] === true) return;
    if (arr[x][y] === 1) return;
    if (x === 6 && y === 6) {
      answer++;
      return;
    }
    for (let [dx, dy] of d) {
      nx = x + dx;
      ny = y + dy;
      if (0 <= nx && nx <= 6 && 0 <= ny && ny <= 6 && !check_table[x][y]) {
        check_table[x][y] = true;
        DFS(x + dx, y + dy);
        check_table[x][y] = false;
      }
    }
  }
  check_table[0][0] = true;
  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));

Solution 풀이

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));

따로 check 배열을 만들지 않고, 그냥 1로 board 배열에 벽을 세워놓았다.
훨씬 깔끔한 것 같다 풀이가.
(방문하기 전에 for문에서 이미 좌표들을 모두 걸러놓고 조건에 맞는 좌표만 방문하는게 훨씬 나은듯)

Solution을 보고 내 풀이 다시 수정

function solution(board) {
  let answer = 0;
  const d = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1]
  ];

  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 (0 <= nx && nx <= 6 && 0 <= ny && 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));

dx와 dy를 let으로 선언을 안해주어서 답이 제대로 안나와서 한참 애를 먹었다. 도대체 내 풀이에선 어떻게 제대로 답이 나온건지..?? 왜 에러가 안뜬거지....