[백준] 9663번: N-Queen (JavaScript, NodeJS)

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력

8

예제 출력

92

정답 풀이

const fs = require('fs');

// 백준 제출 할 때 주석 제거
// const readFileSyncAddress = '/dev/stdin';

// VSC 테스트 할 때 주석 제거
const readFileSyncAddress = 'input.txt';

let input = fs.readFileSync(readFileSyncAddress).toString().trim().split('\n');

input = Number(input[0]);
// 문제 풀이
function solution(input) {
    // 조합 문제
    const visited = new Array(input).fill(0);
    let answer = 0;

    dfs(0);

    function dfs(x) {
        if (x === input) {
            answer += 1;
        } else {
            for (let i = 0; i < input; i++) {
                if (visited[x]) continue;
                visited[x] = i;
                if(check(x)) dfs(x + 1);
                visited[x] = 0;
            }
        }
    }

    function check(x) {
        for (let i = 0; i < x; i++) {
            if (visited[x] === visited[i]) return false;
            if (Math.abs(visited[x] - visited[i]) === x - i) return false;
        }
        return true;
    }

    return answer;
}

// 제출
console.log(solution(input));