[프로그래머스] N-Queen

문제

N-Queen

https://school.programmers.co.kr/learn/courses/30/lessons/12952

 

 

풀이

설명

n개의 퀸을 조건에 만족시키며 배치할 수 있는 방법의 수를 구하는 문제입니다.

 

백트래킹을 통해 해결할 수 있습니다.

 

각 (행, 열)에 퀸이 배치될 수 있는지를 확인하고, 가능하면 다음 퀸으로 넘어갑니다.

모든 퀸이 배치 가능하면 카운트를 증가시킵니다.

 

예시 코드

function solution(n) {
  const board = Array(n).fill(0);
  let answer = 0;

  function canPlace(row, col) {
    for (let i = 0; i < row; i++) {
      if (
        board[i] === col ||
        board[i] - i === col - row ||
        board[i] + i === col + row
      )
        return false;
    }
    return true;
  }

  function backtrack(row) {
    if (row === n) {
      answer++;
      return;
    }

    for (let col = 0; col < n; col++) {
      if (!canPlace(row, col)) continue;
      board[row] = col;
      backtrack(row + 1);
      board[row] = 0;
    }
  }

  backtrack(0);

  return answer;
}