Programmers / Level 2 / N-Queen / JS

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

 

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

---

입출력 예

n	result
4	2

 

 

function solution(n) {
  let result = 0;

  const DFS = (board, row) => {
    // row가 n과 같다는 것은 마지막 행까지 체크했을때 안되는 경우가 없었다는 뜻
    if (row === n) result += 1;
    else {
      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++) {
    // index = row, value = column
    // 예를 들어 index 1에 2가 있다면 1행 2열에 Queen이 있다는 뜻
    let board = Array.from({ length: n + 1 }, () => 0);
    // 첫 행의 i번째 열에 Queen이 있을 경우를 가정하고 DFS 시작
    board[1] = i;
    DFS(board, 1);
  }

  return result;
}