[boj] 9663. N-Queen (node.js)

요약

N이 주어질 때, 가능한 N-Queen 의 조합 개수를 출력하라.

풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
const stdin = fs.readFileSync(filePath).toString().split("\n");

let cnt = 0;
const input = () => {
  return stdin[cnt++];
};

let count = 0;

function NQueen(N, k, arr) {
  if (k == N) {
    count++;
  } else {
    for (let i = 0; i < N; i++) {
      if (isAvailable(arr, i)) {
        arr.push(i);
        NQueen(N, k + 1, arr);
        arr.splice(arr.length - 1);
      }
    }
  }
  return count;
}

function isAvailable(arr, cand) {
  const row = arr.length;
  for (let i = 0; i < row; i++) {
    if (arr[i] == cand || row - i == Math.abs(arr[i] - cand)) {
      return false;
    }
  }
  return true;
}

console.log(NQueen(input(), 0, []));

소스코드는 두 부분으로 나뉜다.

1. NQueen(N, k:행 번호(넣을 자리), arr: 열 번호를 저장할 배열)

• N을 입력으로 받고, k번째 행의 몇 번째 열에 Queen을 넣을지를 arr에 저장하는 recursive function
• 2번 함수에서 true를 반환하는 것이 promising 조건
• k+1에 대해서 반복적으로 수행하고 k == N이면 하나의 조합이 완성되었으므로 count++

2. isAvailable(arr, cand)

• 현재까지 저장되어 있는 arr의 다음 원소로 cand를 입력했을 때 N-Queen의 조건에 위배되는지를 판단하는 bool 함수
• arr 배열 자체가 행을 나타내므로 행 조건은 자연스럽게 만족
• 열 조건과 대각선 조건 두 가지가 pruning 대상이므로 둘 중 하나라도 만족하지 않으면(or) pruning한다.
  • 열 조건: arr[i] == cand
  • 대각선 조건: row - i == Math.abs(arr[i] - cand) (행-행)==(열-열)