30242 N-Qeen(Easy)

문제

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

 N$N$이 주어졌을 때, 퀸을 놓는 방법 한 가지를 출력하는 것은 쉽다.

이 문제에서는 몇 개의 퀸이 이미 놓여있을 때, 퀸을 놓는 방법 한 가지를 출력해 보자.

입력

첫 번째 줄에 정수 N$N$이 주어진다. (1≤N≤20)$(1 \le N \le 20)$ 

두 번째 줄에 정수 Q1$Q_1$, Q2$Q_2$, Q3$Q_3$, ⋯$\cdots$, QN$Q_N$이 주어진다. Qi$Q_i$는 i$i$번째 행에 있는 퀸의 열의 번호를 의미한다. (0≤Qi≤N)$(0 \le Q_i \le N)$ 

만약 Qi$Q_i$가 0이라면 i$i$번째 행에는 퀸이 놓여있지 않다는 뜻이다.

퀸이 서로 공격하는 올바르지 않은 상태의 입력 혹은 N$N$개의 퀸이 모두 놓여있는 경우의 입력은 없다.

출력

첫 번째 줄에 정수 A1$A_1$, A2$A_2$, A3$A_3$, ⋯$\cdots$, AN$A_N$를 출력한다. Ai$A_i$는 i$i$번째 행에 있는 퀸의 열의 번호를 의미한다. (1≤Ai≤N)$(1 \le A_i \le N)$ 

만약 N$N$개의 퀸을 놓을 수 없다면 -1을 출력한다.

==== 

문제분석

https://weeeeey.tistory.com/226

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

 위의  N_Queen 문제에서 이미 퀸이 놓여져 있다는 가정이 추가된 문제이다.

따라서 입력에 주어진 배열에서 각 row별로 체크해나가면서 0이 아니라면 cols와 대각선들의 합과 차에 true를 체크해나가면 된다.

또한 rows 배열을 만들어서 col이 0이 아니라면 그 열을 기록한다.

arr.forEach((col, row) => {
        if (col !== 0) {
            cols[col - 1] = true;
            rows[row] = col - 1;
            diag1[col - 1 + row] = true;
            diag2[row - col + n] = true;
        }
    });

이후 row 0부터 탐색하면서 만약 rows가 -1이 아니라면 해당 행은 퀸이 처음부터 놓여져 있는 것이므로 그 퀸을 정답에 추가해준다.

if (rows[row] !== -1) {
    dfs(row + 1, [...cur, rows[row]]);
    return;
}

이후 row가 n이라는 것은 각 행을 모두 체크한 것이므로 탐색을 종료 후 답을 출력해준다.

정답 코드

const main = (n, arr) => {
    const rows = Array(n).fill(-1);
    const cols = Array(n).fill(false);
    const diag1 = Array(2 * n).fill(false); // x+y
    const diag2 = Array(2 * n).fill(false); // x-y+(n+1)

    arr.forEach((col, row) => {
        if (col !== 0) {
            cols[col - 1] = true;
            rows[row] = col - 1;
            diag1[col - 1 + row] = true;
            diag2[row - col + n] = true;
        }
    });

    const dfs = (row, cur) => {
        if (row === n) {
            console.log(cur.map((v) => v + 1).join(' '));
            process.exit(0);
        }
        if (rows[row] !== -1) {
            dfs(row + 1, [...cur, rows[row]]);
            return;
        }

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

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

    dfs(0, []);
    console.log(-1);
};

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

const n = +input[0];
const arr = input[1].split(' ').map((v) => +v);

main(n, arr);