[js문제풀이] N-Queen

문제

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

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

 

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

제한사항

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

---

입출력 예

n result

4

2

접근 및 풀이

퀸의 공격 유효범위 상하좌우는 비교적 쉽게 구할 수 있었지만 대각선이 문제였다. 대각선의 좌표를 일일이 예외로 넘겨주니 호율성에서 막혔다. 문제 해설을 보니 퀸 각각의 행열과 현재의 행열의 차 절대값이 같으면 대각선이라는 점을 이용할 수 있었다. 

코드

function solution(n) {
  function findQueen(qPosition, curRow) {
    if (curRow === n) return 1;
    let count = 0;
    for (let curCol = 0; curCol < n; curCol++) {
      if (qPosition.find(qPos => {
        const qRow = qPos[0];
        const qCol = qPos[1];
        if (qCol === curCol) return true;
        if (Math.abs(curRow - qRow) === Math.abs(curCol - qCol)) return true;
      })) continue;
      const copyQpos = [...qPosition];
      copyQpos.push([curRow, curCol]);
      count += findQueen(copyQpos, curRow + 1);
    }
    return count;
  }
  return findQueen([], 0);
}

출처

https://programmers.co.kr/learn/courses/30/lessons/12952?language=javascript