1. 미로찾기

ARRAY의 형태의 미로가 주어진다. ARRAY 탐색 능력을 기르는 문제이기도 하다. 독특한 방법으로 접근한다.

좌표를 미리 설정하는 형태이다. X,Y의 좌표를 조합해서 ARRAY의 좌표안에서 누적해서 미로안을 움직인다.

그리고 미로에서 이미 지나간 자리는 1로 처리하여 일종의 발자국을 만든다.

2. 접근방법

• PseudoCode
  • 먼저 dx와 dy의 좌표, 즉 일종의 미로내에서 방향키 역할을 하는 좌표를 array에 담는다
  • dfs함수를 사용한다.
    • 좌표가 map의 끝에 도달하면 answer에 1을 더한다
    • 그게 아니면 next X, next Y를 설정한다음 dfs에 넘긴다.
    • 가다가 갈 수 있는 좌표를 조건으로 설정한다.
    • 이미 지나간 자리는 1로 만들고 다시 돌아올때는 0으로 만들어서 안 가본곳으로 되돌아 갈 수 있도록 한다.

function mazeRunner(maze) {
  let answer = 0;
  let dx = [-1, 0, 1, 0];
  let dy = [0, 1, 0, -1];

  function dfs(hori, vert) {
    if (hori === maze.length - 1 && vert === maze.length - 1) {
      answer++;
    } else {
      for (let i = 0; i < dx.length; i++) {
        let nx = hori + dx[i];
        let ny = vert + dy[i];

        // 갈 수 있는 방향을 파악한다.
        if (nx >= 0 && nx <= 6 && ny >= 0 && ny <= 6 && maze[nx][ny] === 0) {
          maze[nx][ny] = 1;
          dfs(nx, ny);
          maze[nx][ny] = 0;
        }
      }
    }
  }
  maze[0][0] = 1;
  dfs(0, 0);

  return answer;
}

let maze = [
  [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],
];

(-1,0) (0,1) (1,0) (0,-1) 을 더하거나 뺌으로써 maze의 좌표위를 옮겨다니는 방법을 상상못했다.

x 와 y축으로 보고 접근 해야하는구나.

그래서 계속 가다보면 0,6에 도달하게 되는데 이때 갈 수 있는 좌표의 경우를 뽑아보면 (-1,6) (0,7) (1,6) (0,5) 이다. 이중에 부합하는 것은 (1,6) (0,5) 인데 (0,5)는 이미 이전에 1로 되어서 벽이 생겼으므로 갈 수 있는것은 1,6 밖에 없다.

요런식으로 계속 뻗어가는 것이다.

Array 안을 둘러보는 능력이 조금 향상된 것 같다. 이로써 괴물에 잡혀먹지 않을 수 있게 되었다.