[백준] 9663번 N-Queen Javascript(NodeJs)

문제 링크

https://www.acmicpc.net/problem/9663

알고리즘: 백트래킹

문제 요약

크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

풀이 요약

이 문제는 처음 2차원 배열로 접근한다면 시간초과가 발생한다. 그렇기 때문에 Queen의 특징을 봐야 하는데, 퀸의 공격 범위는 퀸이 위치한 행, 열, 대각선이다. 그렇다는 것은 퀸은 하나의 열에 하나씩만 놓을 수 있다. 그러면 우리는 퀸을 하나씩 놓을 때 현재 열에 행에서만 고민하면 되고 그 행에 놓을 때 이미 놓인 퀸의 공격 범위를 체크하면서 놓으면 된다. 이미 놓인 퀸의 행, 열의 공격 범위를 체크하는 것은 매우 쉽다. 그런데 대각선은 조금 생각을 해봐야 하는데. 대각선도 잘 보면 규칙이 있는데 x와 y의 절댓값이 같은 값으로 좌표를 이동한다는 것이다. 그러면 이런 식으로 식을 만들 수가 있다. 이미 놓인 퀸(Qx, Qy),검사할 좌표(x,y)일때 |Qx-x| == |Qy-y|

시간 초과를 피하기 위해서는
=>첫 번째 1차원 배열 이용,
=>두 번째 대각선 판별법
이 두 가지만 유의한다면 시간 초과 없이 잘 출력되는 것을 볼 수 있다.

소스코드

const fs = require('fs');
let N = fs.readFileSync('/dev/stdin').toString().trim() * 1;
let qm_col = new Array(N).fill(false);
let qm_rc = [];
let answel = 0;
DFS(0);
console.log(answel);

function DFS(r) {
    if (r === N) {
        answel += 1;
        return;
    } else {
        for (let c = 0; c < N; c++) {
            if (q_check(r, c)) {
                qm_col[c] = true;
                qm_rc.push([r, c]);
                DFS(r + 1);
                qm_col[c] = false;
                qm_rc.pop();
            }
        }
    }
}

function q_check(x, y) {
    //행 체크
    if (qm_col[y]) {
        return false;
    }
    //대각선 체크
    for (let i = 0; i < qm_rc.length; i++) {
        let [qx, qy] = qm_rc[i];
        if(Math.abs(qx-x) === Math.abs(qy-y)) {
            return false;
        }
    }
    return true;
}