[백준/JS] 9663 N-Queen

문제

📝 문제풀이

참고블로그
공격할 수 없게 놓는 조건

• 모든 퀸의 상하좌우 대각선에 퀸이 있어선 안된다.
  - 끝까지 봐야함

이차원 배열을 선언해서 각 좌표에 놓았을 경우를 모두 생각해주려고 했는데
우선 코드가 너무 복잡해졌고 돌아가지도 않았습니다..

모든 좌표를 볼 필요가 없고 한 행씩 봐주면 됩니다.
따라서 1차원 배열을 선언해서 각 좌표에 어떤 열에 위치해 있는지 저장해주면 됩니다.

좌표 저장 배열

let queen_col = [/*열의 번호들이 저장*/] //각 인덱스는 row의 위치를 의미 

상하좌우에 있나?

queen_col[i] == queen_col[row]

대각선에 있나?

Math.abs(row - i) === Math.abs(queen_col[row] - queen_col[i])

현재 위치가 (a,b) 라 했을때 대각선에 놓이는 좌표들은

1칸 차이

(a+1,b+1)
(a+1,b-1)
(a-1,b+1)
(a-1,b-1)

2칸 차이

(a+2,b+2)
(a+2,b-2)
(a-2,b+2)
(a-2,b-2)

이렇게 됩니다. 결국 행과 열의 거리 차이가 동일하면 대각선입니다!

🧐 정답코드

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

let N = Number(input.shift());
let queen_col = Array(N).fill(-1);
let cnt = 0;

function promising(row) {
  for (let i = 0; i < row; i++) {
    if (
      queen_col[i] == queen_col[row] ||
      Math.abs(row - i) === Math.abs(queen_col[row] - queen_col[i])
    )
      return false;
  }

  return true;
}

function dfs(row) {
  if (row == N) {
    cnt++;
    return;
  }

  for (let col = 0; col < N; col++) {
    queen_col[row] = col;

    if (promising(row)) {
      dfs(row + 1);
    }
  }
}

dfs(0);
console.log(cnt);