Happy Programmer

(1).백준 9663번 N-Queen은 체스판에 퀸을 놓을 수 있는 가짓수를 묻는 문제였다.

저저저번주부터 조금씩 보긴 했는데 중간 중간 풀면서 시간초과도 걸리고

회사에서도 점심시간에 깔짝거리면서 시도도 해봤는데 쉽지 않았다.

어느정도 GPT의 도움을 받아 개선하고 비트마스킹에 대해 학습했는데

기존에 배열에 담는 것과 유사하지만 비트마스킹의 경우 숫자로 보관하기 때문에

제한 숫자가 32 이전의 경우 문제는 없을 것 같고 이번 문제의 제한이 15자리가 최대였기 때문에 사용했다.

기존에 사용한 것 처럼 같은 라인, 대각선, 반대편 대각선을 확인했는데

비트마스킹으로 진행한게 배열을 넘겨주는 것 보다 몇천배 이상 효과적이었다.

이전 코드 방식은 [1,3,0,2]처럼 행 부분은 본인의 index로 치환하고

여태까지 완료된 배열을 넘겨서 push하는 방식으로 진행했는데

아무래도 배열을 넘기는 것 자체가 부담이 큰가보다.

비트마스킹이라는 방법을 배울 수는 있었지만

여태까지 이런 사용법을 쓸 필요가 전혀 없었는데

상위등급 문제를 풀 때는 이렇게 새로운 지식이 늘어날 것 같다는 걱정과 기대감이 생긴다.

const arrLength = 15;
let count = 0;

const recurtion = (row, colCheck, diag1Check, diag2Check) => {
    if (row === arrLength) {
        count++;
        return;
    }

    for (let col = 0; col < arrLength; col++) {
        if (
            !(colCheck & (1 << col)) &&
            !(diag1Check & (1 << (row + col))) &&
            !(diag2Check & (1 << (row - col + arrLength - 1)))
        ) {
            colCheck |= 1 << col;
            diag1Check |= 1 << (row + col);
            diag2Check |= 1 << (row - col + arrLength - 1);
            recurtion(row + 1, colCheck, diag1Check, diag2Check);
            colCheck &= ~(1 << col);
            diag1Check &= ~(1 << (row + col));
            diag2Check &= ~(1 << (row - col + arrLength - 1));
        }
    }
};

recurtion(0, 0, 0, 0);
console.log(count);