백트래킹(Backtracking)

해를 찾는 도중에 해가 될 것 같지 않으면, 되돌아가서 다시 해를 찾는 방법을 말한다. 해가 되지 않으면 그 경로는 쳐낸다.(가지치기) 이렇게 불필요한 경로를 쳐내기 때문에 효율적으로 문제를 처리할 수 있게 된다.(단 가지치기를 잘해야한다.)

백트래킹으로 문제를 풀 경우, DFS로 모든 경우의 수를 탐색하다가 조건문 등을 걸어 해가 절대로 될 수 없는 상황을 정의하고 그런 상황일 경우 탐색을 중지하고 그 이전으로 돌아가 다시 다른 경우를 탐색하게끔 구현할 수 있다.

N-Queen 문제

백트래킹으로 해결할 수 있는 대표적인 문제로 N-Queen 문제가 있다.

백준 - N-Queen 문제

크기가 N x N인 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. 퀸들은 자신의 일직선상(같은행,같은열), 대각선에 있는 퀸을 공격할 수 없다.

• 입력: N

• 출력: 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수

• 배열을 선언함. 배열의 인덱스는 행을 의미

• 배열의 값이 열을 의미. 배열에 같은 값이 있다면 그건 열의 위치가 같다는 것이므로 경우의 수에 포함하지 않음

• 다른 퀸들과 대각선상에 위치해도 경우의 수에 포함시키지 않아야한다. 판단해야하는 퀸의 행번호와 다른 퀸들의 행번호의 차이 = 판단해야하는 퀸의 열번호와 다른 퀸들의 열번호의 차이이면 대각선상에 위치한 것이다.

// 백준 제출용 코드

let N = Number(require('fs').readFileSync('/dev/stdin'));
let result = 0; // 경우의 수를 담을 변수(최종 리턴할 값)
let board = []; // 체스판 배열

function hasConflict(x) {
    for (let i = 0; i < x; i++) {
      // 이전 행을 돌면서 둘 수 없는 퀸인지 체크
      if (board[i] === board[x]) {
        // 같은 열인지 체크
        return true;
      }
      if (Math.abs(board[x] - board[i]) === x - i) {
        // 이전에 둔 퀸들의 대각선에 위치하는지 체크 (x는 i보다 클 수 밖에 없기 때문에 절대값 처리해주지 않아도됨)
        return true;
      }
    }
    return false;
  }

  function findNQueen(row) {
    if (row === N) { // 마지막 행까지 진행됐다는건 경우의 수를 찾았다는 의미이므로 result값을 증가시켜준다.
      result++;
      return;
    }
    for (let col = 0; col < N; col++) {
      board[row] = col;
      if (!hasConflict(row)) {
        // 충돌하지 않는다면
        findNQueen(row + 1);
      }
    }
  }
  findNQueen(0); // 첫번째 행을 넣고 처음으로 findNQueen 함수를 실행
  console.log(result);

// node.js 환경에서 코드 실행 방법
// - js파일 실행 후
// - 입럭값 입력 후 엔터하고
// - Ctrl + D 를 누르면 결과가 나타난다.
const readline = require('readline');

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

let N = 0; // 입력값
let result = 0; // 경우의 수를 담을 변수(최종 리턴할 값)
let board = []; // 체스판 배열

rl.on('line', function (line) {
  N = parseInt(line);
}).on('close', function () {
  function hasConflict(x) {
    for (let i = 0; i < x; i++) {
      // 이전 행을 돌면서 둘 수 없는 퀸인지 체크
      if (board[i] === board[x]) {
        // 같은 열인지 체크
        return true;
      }
      if (Math.abs(board[x] - board[i]) === x - i) {
        // 이전에 둔 퀸들의 대각선에 위치하는지 체크 (x는 i보다 클 수 밖에 없기 때문에 절대값 처리해주지 않아도됨)
        return true;
      }
    }
    return false;
  }

  function findNQueen(row) {
    if (row === N) {
      // 마지막 행까지 진행됐다는건 경우의 수를 찾았다는 의미이므로 result값을 증가시켜준다.
      result++;
      return;
    }
    for (let col = 0; col < N; col++) {
      board[row] = col;
      if (!hasConflict(row)) {
        // 충돌하지 않는다면
        findNQueen(row + 1);
      }
    }
  }
  findNQueen(0); // 첫번째 행을 넣고 처음으로 findNQueen 함수를 실행
  console.log(result);

  process.exit();
});

Ref

• [JavaScript] 백트래킹(Backtracking) 알고리즘
• 알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제
• [백준] 9663번 - N-Queen
• Leetcode 백트래킹 문제들
• 백준 백트래킹 문제들