JavaScript 백트래킹

1. 백트래킹이란?

• 일반적으로 그래프/트리의 모든 원소를 완전 탐색하기 위한 목적으로 사용
• 재귀 함수를 이용해 구현, 단순히 완전 탐색하는 것이 아니라 조건에 따라 유망한 노드로 이동
• 백트래킹을 진행할 때, 경우의 수를 최대한 줄이는 방법
  : 이전까지 경우와 상충되지 않는 조건을 만족하는 위치에 대해서만 재귀 함수를 호출
  1. 재귀 함수를 통해 모든 경우의 수를 다 찾은 뒤에, 각 경우마다 가능한지 검사하는 방법
  2. 유망한 경우에 대해서만 재귀 함수를 호출하는 방법
     ==> 2번 방법이 더 효율적이다.
• N-queen

let n = 8;
let queens = [];

function possible(x, y) {
  for (let [a, b] of queens) {	// 현재까지 놓았던 위치를 하나씩 확인
    if (a == x || b == y) return false;	// 행이나 열이 같다면 놓을 수 없음
    if (Math.abs(a - x) == Math.abs(b - y)) return false;	// 대각선에 위차한 경우 놓을 수 없음
  }
  return true;
}

let cnt = 0;
function dfs(row) {
  if (row == n) cnt += 1;	// 퀀을 N개 배치할 수 있는 경우 카운트
  for (let i = 0; i < n; i++) {	// 현재 행(row)에 존재하는 열을 하나씩 확인
    if (!possible(row, i)) continue;	// 현재 위치에 놓을 수 없다면 무시
    queens.push([row, i]);	// 현재 위치에 배치
    dfs(row + 1);	// 재귀 함수 호출
    queens.pop();	// 현재 위치에서 퀸 제거
  }
}
dfs(0);
console.log(cnt);