[JS] 코딩 테스트 문제 : 미로탐색 [DFS]

문제 : 미로탐색(DFS)

문제 설명

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 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	도착

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

▣ 입력설명

7*7 격자판의 정보가 주어집니다.

▣ 출력설명

첫 번째 줄에 경로의 가지수를 출력한다.

▣ 입력예제 1

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

8

내코드

function solution(board) {
  let answer = 0; // 미로를 탈출한 경우의 수를 의미하는 정답 변수

  // 방문 여부를 저장할 2차원 배열 tempArr 선언 후 모두 0 값으로 초기화
  // 배열의 값이 0 인 경우 방문하지 않은 것을 의미, 1인경우 방문한 것을 의미
  let tempArr = Array.from(Array(7), () => new Array(7).fill(0));
  tempArr[0][0] = 1; // 첫 시작위치는 1로 초기화

  // 격자의 좌표 즉 2 차원 배열의 주소값을 의미할 x,y 를 인자로 가지는 재귀함수 DFS 선언
  function DFS(y, x, arr = []) {
    // 탈출 도착 좌표 (7,7) 즉 board[6][6] 에 도착한 경우에 미로를 탈출했으므로 answer 변수를 1 증가
    // ※ 재귀적으로 함수 호출 중 미로에 이동 경로를 저장하여 확인만을 위한 임시 배열 인자 arr 
    if (x === 6 && y === 6) {
      answer++;
      console.log(...arr);
      return;
    }

    // 특정 방향(상하좌우)으로 이동 가능한 조건
    // 1. 이동할 위치가 지금까지 방문하지 않은 위치인 경우 (tempArr에 위치한 값이 0인 경우)
    // 2. 이동할 위치가 이동할 수 있는 위치인 경우 (board에 위치한 값이 0인 경우)

    // 상 이동 2차원 배열 기준 현재 위치에서 y - 1 위치를 참고해 이동 가능 여부를 판단
    if (y > 0 && tempArr[y - 1][x] === 0 && board[y - 1][x] === 0) {
      tempArr[y - 1][x] = 1; // 방문 여부 업데이트
      DFS(y - 1, x, [...arr, [y - 1, x]]); // 이동한 위치를 매개변수로 재귀적으로 함수를 호출
      tempArr[y - 1][x] = 0; // 방문 여부 초기화
    }

    // 하 이동 2차원 배열 기준 현재 위치에서 y + 1 위치를 참고해 이동 가능 여부를 판단
    if (y < 6 && tempArr[y + 1][x] === 0 && board[y + 1][x] === 0) {
      tempArr[y + 1][x] = 1; // 방문 여부 업데이트
      DFS(y + 1, x, [...arr, [y + 1, x]]); // 이동한 위치를 매개변수로 재귀적으로 함수를 호출
      tempArr[y + 1][x] = 0; // 방문 여부 초기화
    }

    // 좌 이동 2차원 배열 기준 현재 위치에서 x - 1 위치를 참고해 이동 가능 여부를 판단
    if (x > 0 && tempArr[y][x - 1] === 0 && board[y][x - 1] === 0) {
      tempArr[y][x - 1] = 1; // 방문 여부 업데이트
      DFS(y, x - 1, [...arr, [y, x - 1]]); // 이동한 위치를 매개변수로 재귀적으로 함수를 호출
      tempArr[y][x - 1] = 0; // 방문 여부 초기화
    }

    // 우 이동 2차원 배열 기준 현재 위치에서 x + 1 위치를 참고해 이동 가능 여부를 판단
    if (x < 6 && tempArr[y][x + 1] === 0 && board[y][x + 1] === 0) {
      tempArr[y][x + 1] = 1; // 방문 여부 업데이트
      DFS(y, x + 1, [...arr, [y, x + 1]]); // 이동한 위치를 매개변수로 재귀적으로 함수를 호출
      tempArr[y][x + 1] = 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));

풀이

1. 방문 여부를 저장할 2차원 배열 tempArr 선언 후 모두 0 값으로 초기화, 이 배열의 값이 0 인 경우 방문하지 않은 것을 의미하고 1인 경우 방문한 것을 의미 합니다.
2. 격자의 좌표 즉 2 차원 배열의 주소 값을 의미할 x,y 를 인자로 가지고 주어진 위치에서 상하좌우로 이동하는 모든 경우를 재귀적으로 처리하는 재귀 함수 DFS 선언
3. 특정 방향으로 이동하기 위해 이동할 위치가 지금까지 방문하지 않은 위치인 경우(tempArr 배열의 해당 위치에 위치한 값이 0인 경우)와 이동할 수 있는 위치인 경우(board배열의 해당 위치에 위치한 값이 0인 경우) 를 판단
4. 위 경우를 모두 만족할 경우 방문 여부를 업데이트 (tempArr 배열의 해당 위치에 값을 1 로 변경) 후 방문한 위치를 기준으로 매개변수로 재귀적으로 함수를 호출 후 방문이 종료된 후 tempArr 초기화를 위해 방문 여부를 초기화 합니다. (tempArr 배열의 해당 위치에 값을 0 로 변경)
5. 재귀 함수가 실행되는 과정 중 탈출 도착 좌표 (7,7) 즉 board[6][6] 에 도착한 경우에 미로를 탈출했으므로 answer 변수를 1 증가하고 함수를 종료합니다.

다른 해결 방법

// 답안지 방법
function solution(board) {
  let answer = 0; // 미로를 탈출한 경우의 수를 의미하는 정답 변수

  // 특정 방향(상하좌우)으로 이동하기 위해 2차원 배열에서 필요한 주소의 변경값을 각각 가지는 배열 dx, dy 를 선언
  // [dx[0], dy[0]] = [-1, 0] 는 상 이동
  // [dx[1], dy[1]] = [0, +1] 는 우 이동
  // [dx[2], dy[2]] = [+1, 0] 는 하 이동
  // [dx[3], dy[3]] = [0, -1] 는 좌 이동
  let dx = [-1, 0, 1, 0];
  let dy = [0, 1, 0, -1];

  // 탈출 도착점에 도착하는 모든 경우의 수를 구하기 위해 현재 위치 값을 의미하는 인자 nx, ny 를 기준으로 4가지 방향으로 이동을 반복하며 재귀적으로 방문 경로를 확인하는 함수 DFS 선언
  function DFS(x, y) {
    // 탈출 도착 좌표 (7,7) 즉 board[6][6] 에 도착한 경우에 미로를 탈출했으므로 answer 변수를 1 증가
    if (x === 6 && y === 6) answer++;
    else {
      for (let k = 0; k < 4; k++) {
        // 특정 위치로 이동
        // nx 와 ny 값을 dx,dy 의 k 번째 값을 활용해 특정 방향으로 이동한 위치의 주소값으로 변경
        let nx = x + dx[k];
        let ny = y + dy[k];

        // nx >= 0 && nx <= 6 && ny >= 0 && ny <= 6 : 미로를 벗어나지 않는 경우
        // board[nx][ny] === 0 : 이동할 수 있는 통로인 경우
        // 위 경우들을 모두 만족하는 경우 이동 가능 여부로 판단
        if (nx >= 0 && nx <= 6 && ny >= 0 && ny <= 6 && board[nx][ny] === 0) {
          board[nx][ny] = 1; // 특정 위치에 방문한 경우 다시 돌아오는 경우를 방지하기 위해 1 값으로 변경
          DFS(nx, ny); // 이동한 위치를 매개변수로 재귀적으로 함수를 호출
          board[nx][ny] = 0; // 방문과정이 종료된후 방문한 위치를 다시 0 으로 변경
        }
      }
    }
  }

  // 시작 위치 값 1로 초기화
  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));

풀이

1. 특정 방향(상하좌우)으로 이동하기 위해 2차원 배열에서 필요한 주소의 변경 값을 각각 가지는 배열 dx, dy 를 선언
2. [dx[0], dy[0]] = [-1, 0] 는 상 이동을 의미, [dx[1], dy[1]] = [0, +1] 는 우 이동을 의미, [dx[2], dy[2]] = [+1, 0]는 하 이동을 의미, [dx[3], dy[3]] = [0, -1] 는 좌 이동을 의미
3. 탈출 도착점에 도착하는 모든 경우의 수를 구하기 위해 현재 위치 값을 의미하는 인자 nx, ny 를 기준으로 4가지 방향으로 이동을 반복하며 재귀적으로 방문 경로를 확인하는 함수 DFS 선언
4. nx 와 ny 값을 dx, dy 의 k 번째 값을 활용해 특정 방향으로 이동한 위치의 주소 값으로 변경
5. 이동할 위치가 미로를 벗어나지 않는 경우 (nx >= 0 && nx <= 6 && ny >= 0 && ny <= 6)와 이동할 수 있는 통로인 경우(board[nx][ny] === 0) 인지를 판단
6. 위 경우를 모두 만족할 때 특정 위치에 다시 돌아오는 경우를 방지하기 위해 방문한 위치(board[nx][ny] 값)를 1로 변경 후 이동한 위치를 매개변수로 재귀적으로 함수 호출, 이후 방문 과정이 종료된 후 방문한 위치(board[nx][ny])를 다시 0 으로 변경해 초기화
7. 재귀 함수가 실행되는 과정 중 탈출 도착 좌표 (7,7) 즉 board[6][6] 에 도착한 경우에 미로를 탈출했으므로 answer 변수를 1 증가하고 함수를 종료합니다.

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/unit/64154