Node.js) 백준 1799번: 비숍

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

1799번: 비숍

const input = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n');
const N = +input.shift();
const board = input.map((v) => v.split(' ').map(Number));

const cross = Array.from(Array(2 * N), () => []);
for (let i = 0; i < N; i++) {
	for (let j = 0; j < N; j++) {
		if (board[i][j] == 1) cross[i + j].push([i, j]);
	}
}

// console.log(cross);

let visited = Array.from(Array(2 * N), () => false);

let answer = 0;
let max = 0;

function dfs(n, cnt) {
	if (max >= cnt + Math.ceil((2 * N - 1 - n) / 2)) return;

	if (n >= 2 * N - 1) {
		max = Math.max(cnt, max);
		return;
	}

	cross[n].forEach(([i, j]) => {
		// console.log(i - j + N);
		if (visited[i - j + N] == false) {
			visited[i - j + N] = true;
			dfs(n + 2, cnt + 1);
			visited[i - j + N] = false;
		}
	});
	dfs(n + 2, cnt);
}
dfs(0, 0);
answer += max;
max = 0;
dfs(1, 0);
answer += max;
console.log(answer);

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