9663 N-Queen (자바스크립트)

문제

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

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

입력

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

출력

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

 

===

문제 분석

특정 위치에 퀸을 놓았을 때, 그 다음으로 퀸을 놓을 수 없는 위치를 파악하는 문제이다.

만약 퀸을 2,2 에 놓았다면,

1. 같은 열인 2 에는 모두 퀸을 놓을 수 없다 => 세로 선

2. [0,0] [1,1] [3.3] [4,4] 에 놓을 수 없다. => 왼쪽 위에서 오른쪽 아래로 향하는 대각선

3. [0,4] [1,3] [3,1] [4,0] 에 놓을 수 없다. => 오른쪽 위에서 왼쪽 아래로 향하는 대각선

4. 같은 행인 2에는 놓을 수 없다 => 가로선

1번과 4번은 직관적이라 체크하기 쉬운데 2,3번은 특정 규칙을 찾지 못하면 2차원 배열을 만들어서 그래프로 2중 반복문으로 체크를 할 수 있다. 

2번에서 행-열이 0인 것을 캐치하고 

3번에서 행+열이 4인 것을 캐치했다면 다른 특정 좌표에서는 어떤지 체크해본다.

==> 만약 2,3 에 퀸을 놓았다면 

2. [0,1] [1,2] [3,4] [4,5] -> 왼쪽 위에서 오른쪽 아래

3. [0,5] [1,4] [3,2] [4,1]  -> 오른쪽 위에서 왼쪽 아래 

2번의 행-열 은 1로 일정

3번의 행+열은 5로 일정

---> 즉, 특정 좌표에서 왼쪽 위에서 오른쪽 아래로 향하는 대각선은 특정 좌표의 행-열이 같은 값을 가지고,

오른쪽 위에서 왼쪽 아래로 향하는 대각선은 특정 좌표의 행+열과 같은 값을 가진다. 

이를 통해 2차원 배열로 그래프를 만들어서 놓을 수 없는 것을 체크하는 것이 아닌

대각선 체크를 위한 배열 두개를 선언하는 방법을 사용할 수 있다.

이 때, 행-열은 -n~n의 값을 가지므로 배열을 선언할 때 2n의 길이를 가진 뒤 행-열+(n-1)을 통해 인덱스 에러를 피해준다.

행+열 또한 0~2n의 값을 가지므로 배열을 선언할 때 2n의 길이를 만들어준다.

    const cols = Array(n).fill(false);
    const diag1 = Array(2 * n).fill(false);
    const diag2 = Array(2 * n).fill(false);

정답코드

const main = (n) => {
    let answer = 0;
    const cols = Array(n).fill(false);
    const diag1 = Array(2 * n).fill(false);
    const diag2 = Array(2 * n).fill(false);

    const dfs = (row) => {
        if (row === n) {
            answer++;
            return;
        }

        for (let col = 0; col < n; col++) {
            if (cols[col] || diag1[row - col + n - 1] || diag2[row + col])
                continue;

            cols[col] = diag1[row - col + n - 1] = diag2[row + col] = true;
            dfs(row + 1);
            cols[col] = diag1[row - col + n - 1] = diag2[row + col] = false;
        }
    };

    dfs(0);
    console.log(answer);
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
main(n);