미로탐색

문제설명

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은 지나 갈 수 있는 통로.

1은 지나 갈 수 없는 벽.

0,0 부터 시작해서

7,7로 도착하는 경우의 수를 구하는 함수를 완성하세요.

function solution(board) {
  
  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));

접근방법

도저히 접근 할 수가 없었다.

풀이를 듣고 이해를 하긴 했는데,

설명하자니 막막하다.

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

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

우선 answer에 0을 매겨 놓는다.

dx 와 dy 는 이동칸수를 나타낸다

x는 가로축 이고 y는 세로 축이다

dx[0], dy[0] 은 -1, 0 을 의미한다.

 

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

if 문을 이용해 answer에 카운트를 해줄 조건문을 만든다.

x와 y가 모두 6일때

즉 6,6에 도달하면 answer에다가 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++;
      return;
    }

    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (nx >= 0 && nx <= 6 && ny >= 0 && ny <= 6 && board[nx][ny] === 0) {
        board[x][y] = 1;
        DFS(nx, ny);
        board[x][y] = 0;
      }
    }
  }
  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)); //8

nx 는 next x 를 의미한다.

현재의 x값에다가 dx[i]값을 더해준다.

함수의 매개변수에 0,0이 할당 되었으니

x 와 y는 모두 0 이고

nx와 ny는 각각 dx[i] dy[i]를 더해준 값이 된다.

i는 for문을 통해 0부터 3까지 증가한다.

nx와 ny 가 0이상 6이하 이고,

board[nx][ny]가 0이면

board[x][y]에 1을 체크하고

재귀함수를 통해 DFS(nx,ny)를 호출하고 반복한다.

 

**

board[x][y] = 1 과

board[x][y] = 0 은

board[nx][ny] = 1

board[nx][ny] = 1

로 바꿔도 결과에 영향이 없었다.