[JavaScript] 프로그래머스 N-Queen LEVEL3

문제출처

let answer = 0;

const dfs = (n, y, col, diag1, diag2) => {
    if (y === n) {
        answer++;
        return;
    }
    
    for (let x=0; x<n; x++) {
        if (col.includes(x) || diag1.includes(x + y) || diag2.includes(x - y)) continue;
        col.push(x);
        diag1.push(x + y);
        diag2.push(x - y);
        dfs(n, y + 1, col, diag1, diag2);
        col.splice(col.indexOf(x), 1);
        diag1.splice(diag1.indexOf(x + y), 1);
        diag2.splice(diag2.indexOf(x - y), 1);
    }
};

function solution(n) {
    dfs(n, 0, [], [], []);
    return answer;
}

풀이

백트래킹 문제이다.

행을 한칸씩 내려가면서 y === n일때까지 내려갈 수 있는지 탐색하는데,
만약 중간에서 끊기면 다시 위로 올라와서 다른 열을 탐색한다.

참고