백트래킹

• 근래에 꾸준한 공부 습관을 다시금 들이고자 틈틈이 알고리즘 문제를 풀고 있다.
• 그러던 와중, '백트래킹'에 대해 조금 공부하게 되어 개념과 푼 문제를 간단하게 정리해보려 한다.

---

백트래킹(Backtracking)

• 현재 상황에서 탐색 가능한 모든 경로를 다 탐색하다, 조건에 맞지 않는 경로를 탐색하게 될 경우 다시 뒤로 돌아가서 다른 경로를 탐색하는 알고리즘.
• 이 때 해결하려는 문제는 트리 구조로 표현되며, 이를 탐색하는 데에는 깊이 우선 탐색을 사용한다.
• DFS와는 달리 조건(한정 조건이라고 하는 듯)에 맞지 않는 해가 나오면 이전으로 돌아가기 때문에 최종적으로 탐색 시간이 줄어든다는 특징이 있음.

 

  백트래킹을 접하며 참고했던 어느 블로그에서 DFS와 백트래킹을 유사점(교차점)이 있는 교집합 관계같다 표현한 것을 본 적이 있는데, 내 경우에도 비슷한 느낌을 받았다.

 

 

문제 풀이

  백트래킹 문제 중 가장 유명한 문제가 N-Queen 문제다. 이미 많은 블로그에서 소개하고 있고, 나 또한 백트래킹을 공부하며 자주 눈에 들어왔다. 

위키피디아에서 설명하는 N-Queen 문제(여기선 8 queens puzzle)

  나 또한 백트래킹의 개념을 정리하기 위해 풀어봤기에 대강의 풀이를 공유한다.

---

  N개의 퀸을 N × N 크기의 체스판에 서로를 공격하지 못하도록 배치하는 문제가 N-Queen문제다.

  체스에서 퀸은 가로/세로/대각선 방향으로 원하는 칸 수만큼 움직일 수 있기 때문에, 달리 말하면 N개의 퀸들을 다른 퀸의 가로/세로/대각선 방향에서 벗어나는 칸에 배치하는 문제라고 할 수 있다.

  체스판을 N × N의 2차원 배열로 구성한다고 가정했을 때, 다음과 같은 과정으로 퀸들이 서로의 공격 범위에 위치하지 않게 배치했다.

1. 한 퀸이 자리한 위치의 행(가로)에는 다른 퀸이 올 수 없다. 배열의 관점에서 생각하면, 배열의 각 행에 한 개의 퀸을 둔다고 할 수 있다.
2. 퀸을 배치할 행이 결정되면 그 행 전체를 순회하며, 각 칸에 퀸을 배치했을 때 이전에 둔 퀸에게 공격받을 수 있는지 없는지를 검사한다.
3. 이 때 가로는 이미 겹치지 않도록 배치하기 때문에, 세로와 대각선 방향에 퀸이 위치했는지만 검사하면 된다.

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

let input;
let answer = 0;
let board;

// 해당 칸에 퀸을 둘 수 있는지 없는지 검사하는 함수
const checkForQueen = (row, col) => {
  if (row === 0) return true;

  // Check for column
  for (let i = 0; i < row; i++) {
    if (board[i][col] === 1) return false;
  }

  // Check for diagonal
  let r = row;
  if (col != input - 1) {
    let right = col;
    while (right < input && r - 1 >= 0) {
      if (board[--r][++right] === 1) return false;
    }
  }

  if (col != 0) {
    let left = col;
    r = row;
    while (left >= 0 && r - 1 >= 0) {
      if (board[--r][--left] === 1) return false;
    }
  }

  return true;
};

const backTrack = (num) => {
  if (num === input) {
    // console.log(board);
    answer++;
  } else {
    for (let i = 0; i < input; i++) {
      // 한 행에 대해 무조건 한 개의 퀸을 놓아야 함.
      // 한 행 -> for의 반복으로 해결
      // 별도의 방법으로 놓으려는 자리의 각 열과 대각선에 퀸이 있는지 확인해야 함.
      if (checkForQueen(num, i)) {
        board[num][i] = 1;
        backTrack(num + 1);
        board[num][i] = 0;
      }
    }
  }
};

rl.on("line", (line) => {
  input = parseInt(line);
}).on("close", function () {
  board = new Array(input);
  for (let i = 0; i < input; i++) {
    board[i] = new Array(input);
    board[i].fill(0);
  }

  backTrack(0);

  console.log(answer);

  process.exit();
});