[알고리즘 연습] 백준 14712 (넴모넴모, 자바스크립트)

문제

14712번: 넴모넴모 (Easy)

---

풀이

• 모든 위치에 넴모를 배치한 경우 그렇지 않은 경우 2가지 탐색을 모두 진행한다.

소스 코드

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

const [N, M] = input[0].split(" ").map(Number);
const arr = Array.from({ length: N }, () => Array(M).fill(0));
let answer = 0; // 2 * 2 사각형을 이루지 않는 모든 배치의 가짓수

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

function dfs(x, y) {
  if (x === N) {
    for (let i = 0; i < N - 1; i++) {
      for (let j = 0; j < M - 1; j++) {
        if (
          arr[i][j] === 1 &&
          arr[i][j] === arr[i + 1][j] &&
          arr[i][j] === arr[i][j + 1] &&
          arr[i][j] === arr[i + 1][j + 1]
        ) {
          return;
        }
      }
    }

    answer += 1;
    return;
  }

  const nx = y + 1 === M ? x + 1 : x;
  const ny = y + 1 === M ? 0 : y + 1;

  // 해당 위치에 넴모를 배치하거나 안하거나
  arr[x][y] = 1;
  dfs(nx, ny);

  arr[x][y] = 0;
  dfs(nx, ny);
}