백준 node.js 1799번 비숍 백트래킹 JavaScript JS

1799번: 비숍

문제풀이

1. 체스판을 두 개의 체스판으로 나누어 생각하는게 문제의 포인트입니다.
2. 체스판은 하얀색과 검은색, 두 가지 색의 격자로 이루어 져 있습니다.
3. 비숍은 대각선으로만 움직이기 때문에 검은색 자리에선 하얀색 자리에 영향을 줄 수 없기 때문에 나누어 생각하여 시간 복잡도를 현저히 줄일 수 있습니다.

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

let white = 0;
let black = 0;
whiteBoard([]);
blackBoard([]);
console.log(white+black);

function whiteBoard(Barr) {
  const len = Barr.length;
  const latY = Barr[len - 1] ? Barr[len - 1][0] : 0;

  for (let a = latY; a < N; a++) {
    for (let b = a % 2 === 1 ? 1 : 0; b < N; b += 2) {
      if (board[a][b] === 1) {
        let pass = true;
        for (let [a2, b2] of Barr) {
          if (Math.abs(a - a2) === Math.abs(b - b2)) {
            pass = false;
          }
        }
        if (pass) whiteBoard([...Barr, [a, b]]);
      }
    }
  }

  if (white < len) white = len;
}

function blackBoard(Barr) {
  const len = Barr.length;
  const latY = Barr[len - 1] ? Barr[len - 1][0] : 0;

  for (let a = latY; a < N; a++) {
    for (let b = a % 2 === 0 ? 1 : 0; b < N; b += 2) {
      if (board[a][b] === 1) {
        let pass = true;
        for (let [a2, b2] of Barr) {
          if (Math.abs(a - a2) === Math.abs(b - b2)) {
            pass = false;
          }
        }
        if (pass) blackBoard([...Barr, [a, b]]);
      }
    }
  }

  if (black < len) black = len;
}

---

흰 부분과 검은 부분으로 나누어 생각하지 못한다면 영원히 풀 수 없었을 것 같네요..

풀 수 있을 법 해서 꽤 오래 붙잡고 있었는데..

역시 문제 풀 때 3시간 이상 붙잡고 있는 건 현명하지 못한 방법인 것 같습니다!