[JavaScript/section 9] 03 - 미로 탐색

📌 03 - 미로 탐색(DFS)

7*7 격자판 미로를 탈출하는 경로의 가짓수를 출력하는 문제이다. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7) 좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지 이다.

 

📝 풀이 방법

nx - 이동할 행, ny - 이동할 열

• 상하좌우로만 움직일 수 있으므로 움직일 수 있는 경우의 수는 4가지이다.
• 재귀를 돌면서 다음에 이동할 좌표가 격자판을 벗어나지 않는지 확인한 다음 이동이 가능한 통로가 맞는지 확인 해야 한다.
• board[nx][ny] (이동할 좌표)가 0이라면 이동이 가능한 것이므로 이동하고 이동했음을 나타내기 위해 board[nx][ny]를 1로 재 할당한다. (왔던 길을 바로 돌아가는 불상사를 막기 위함)
• DFS() 함수가 종료하고 나면 board[nx][ny]를 0으로 재 할당함으로써 다음에 이동이 가능할 수 있도록 해준다. (백트래킹)
• x와 y가 6이라면 탈출 도착점(6, 6) 좌표에 있는 것이므로 answer++을 해준다.

주의 사항❗ 재귀 함수를 호출하기 전에 board[0][0] (출발점)을 1로 초기화 해야 한다.

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 i = 0; i < 4; i++) {
        let nx = x + dx[i];
        let ny = y + dy[i];

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

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