[소프티어] 순서대로 방문하기 | JavaScript | 백트래킹

문제출처

1. 문제

Sam은 팀장님으로부터 차량이 이동 가능한 시나리오의 수를 찾으라는 업무 지시를 받았습니다. 이동은 숫자 0과 1로만 이루어져 있는 n x n 크기의 격자 위에서 일어납니다. 숫자 0은 빈 칸을 의미하며, 숫자 1은 해당 칸이 벽으로 막혀 있음을 의미합니다. 아래는 n이 3인 경우의 예시입니다.

0 0 0
0 0 0
0 0 1

차량은 n x n 격자 내에서 m개의 지점을 순서대로 방문하려고 합니다. 이 때 이동은 항상 상하좌우 중 인접한 칸으로만 이동하되 벽은 지나갈 수 없으며, 한 번 지났던 지점은 다시는 방문해서는 안 됩니다. 이러한 조건 하에서 차량이 이동 가능한 서로 다른 가지 수를 구하는 프로그램을 작성해보세요.

방문해야 하는 지점의 첫 지점이 출발점이며, 마지막 지점이 도착점임에 유의합니다.

위의 예에서 m = 3, 방문해야 하는 지점이 순서대로 (3행, 1열), (1행, 2열), (2행, 3열)이라면, 다음과 같이 5가지의 시나리오가 가능합니다.

1. (3행, 1열) → (3행, 2열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

2. (3행, 1열) → (3행, 2열) → (2행, 2열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

3. (3행, 1열) → (2행, 1열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

4. (3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

5. (3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (2행, 2열) → (2행, 3열)

제약조건

[조건 1] 2 ≤ n ≤ 4
[조건 2] 2 ≤ m ≤ n2

입력형식

첫 번째 줄에는 격자의 크기를 나타내는 n과 순서대로 방문해야 하는 칸의 수 m이 공백을 사이에 두고 주어집니다.

두 번째 줄부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 수가 공백을 사이에 두고 주어집니다. 주어지는 수는 0 또는 1이며, 0은 빈 칸을 1은 벽을 의미합니다.

n + 2 번째 줄부터는 m개의 줄에 방문해야 할 m개의 칸의 위치 (x, y) 쌍이 공백을 사이에 두고 한 줄에 하나씩 순서대로 주어집니다. 주어지는 칸에 벽이 있는 경우는 없으며, 동일한 칸이 여러 번 주어지는 경우는 없다고 가정해도 좋습니다.

출력형식

차량이 m개의 지점을 순서대로 방문할 수 있는 서로 다른 방법의 수를 출력합니다. 만약 가능한 방법이 없다면 0을 출력합니다.

입력예제1

3 3
0 0 0
0 0 0
0 0 1
3 1
1 2
2 3

출력예제1

5

2. 풀이

백트래킹을 잘 사용하는 편은 아니지만 이번 문제를 통해 백트래킹에 대한 이해도가 조금 올라갔다.

아래와 같은 방식으로 문제를 풀었다.

• backTracking() 함수를 이용하여 goals 배열에 저장된 칸을 순서대로 방문하며 경로의 수를 구함
• backTracking()
  • 인자로 현재 목표로 하는 칸의 인덱스(idx), 현재 위치(x, y) 받음
  • idx 값을 확인해서 마지막으로 방문해야 할 칸에 도착했다면 카운트를 증가시키고 종료
  • idx가 마지막 값이 아니라면 backTracking() 호출
• 현재 위치에서 상하좌우 이동 가능한지 확인 후, 이동 가능하다면 visited 배열 업데이트, backTracking() 호출
  • 호출이 완료되면 visited 배열 다시 업데이트 후 다음 방향으로 이동

전체 코드는 아래와 같다.

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let lines = [];

rl.on("line", (line) => {
  lines.push(line.split(" ").map(Number));
}).on("close", () => {
  const [n, m] = lines[0]; // 격자의 크기, 순서대로 방문해야 하는 칸의 수
  let board = lines.slice(1, n + 1); // 격자
  let goals = lines.slice(n + 1).map((arr) => arr.map((val) => val - 1)); // 방문해야 할 칸의 위치 (x,y)
  
  let visited = Array.from({ length: n }, () => Array(n).fill(false));
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  let cnt = 0;

  visited[goals[0][0]][goals[0][1]] = true;
	
  // 유효한지 검사
  function isValid(x, y) {
    return (
      x > -1 && x < n && y > -1 && y < n && board[x][y] === 0 && !visited[x][y]
    );
  }
	
  // 백트래킹 탐색
  function backTracking(idx, x, y) {
    // 마지막으로 방문해야 할 칸에 도달한 경우
    if (idx === goals.length - 1) {
      if (goals[idx][0] === x && goals[idx][1] === y) {
        cnt++;
        return;
      }
      // 다음 칸을 목표로 백트래킹
    } else if (goals[idx][0] === x && goals[idx][1] === y) {
      backTracking(idx + 1, x, y);
    }
	
    // 상하좌우 이동 가능하면 방문, 백트래킹 탐색
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      
      if (isValid(nx, ny)) {
        visited[nx][ny] = true;
        backTracking(idx, nx, ny);
        visited[nx][ny] = false;
      }
    }
  }

  backTracking(1, goals[0][0], goals[0][1]);

  console.log(cnt);
  process.exit();
});