백준 / 백트래킹 / 9663번 / N-Queen / JS

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1 

8

예제 출력 1 

92

 

 

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

const N = +input.shift();

function solution(N) {
  let result = 0;
  let board = Array.from({ length: N + 1 }, () => 0);

  const DFS = (board, row) => {
    if (row === N) result += 1;

    for (let i = 1; i <= N; i++) {
      board[row + 1] = i;
      if (isValid(board, row + 1)) DFS(board, row + 1);
    }
  };

  const isValid = (board, row) => {
    for (let i = 1; i < row; i++) {
      if (board[row] === board[i]) return false;
      if (Math.abs(row - i) === Math.abs(board[row] - board[i])) return false;
    }

    return true;
  };

  for (let i = 1; i <= N; i++) {
    board[1] = i;
    DFS(board, 1);
  }

  return result;
}

const result = solution(N);
console.log(result);

---

코드를 설명해줄 더 자세한 주석과 설명을 보고 싶다면 밑 게시글을 클릭해주세요.

(Programmers에 있는 같은 문제 풀이입니다.)

2022.10.01 - [PS/Programmers] - Programmers / Level 2 / N-Queen / JS

Programmers / Level 2 / N-Queen / JS