[알고리즘/인프런] 미로탐색

문제

---

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격
자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

 

 

 

풀이

---

function solution(arr) {
  const n = arr.length;
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  let answer = 0;

  function DFS(x, y) {
    if (x === n - 1 && y === n - 1) {
      answer += 1;
    } else {
      for (let i = 0; i < 4; i++) {
        const nx = x + dx[i]; // 다음 x 좌표 
        const ny = y + dy[i]; // 다음 y 좌표 

        if (nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] === 0) {
          arr[nx][ny] = 1;
          DFS(nx, ny);
          arr[nx][ny] = 0;
        }
      }
    }
  }
  
  arr[0][0] = 1; // 시작점 방문 표시 
  DFS(0, 0);
  return answer;
}

입력으로 받은 배열에서 네 방향을 확인했을 때 가능한 지점인 경우 이동하면서 도착점까지 가는 방법을 찾는다. 가능한 지점은 arr 배열에서 index가 존재하고 아직 방문하지 않은 지점(arr[nx][ny] === 0)이다.

시작점을 방문 표시 해주지 않아서 자꾸 더 많은 경우의 수를 출력했다. 꼭 시작점 방문 표시를 해줘야겠다. 또 dx는 행에서, dy는 열에서의 이동을 의미한다는 것에 유의해야겠다.