백준 9663번 JavaScript

백준9663번 node.js

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const n = Number(input[0]);
const queens = [];

function possible(row, col) { //해당 위치에 퀸 놓을 수 있는지 확인
  for (let [x, y] of queens) {
    if (x === row || y === col) return false; //행이나 열이 같을 경우
    if (Math.abs(x - row) === Math.abs(y - col)) return false; //대각선으로 놓는 경우
  }
  return true;
}
let count = 0;
function dfs(row) {
  if (row === n) count += 1;  //n개의 퀸을 놓았을 때 카운트
  for (let col = 0; col < n; col += 1) {  //열을 모두 확인
    if (!possible(row, col)) continue; //해당 위치 놓을 수 없는 경우, 다음으로
    queens.push([row, col]);  //퀸의 현재 위치
    dfs(row + 1);
    queens.pop();  //현재위치 퀸 빼기
  }
}

dfs(0);
console.log(count);

백트래킹은 기본적으로, 가능한 노드에 대하여 계속하여 재귀적으로 함수를 호출합니다.
상태 트리의 가장 아래 부분까지 탐색을 하므로 dfs와 유사하다고 볼 수 있습니다.

퀸은 같은 행에 있는 경우, 같은 열에 있는 경우, 대각선에 있는 경우에 놓을 수 없기 때문에 가능 여부를 확인해주었습니다.