백준 9663 N-Queen

문제

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

9663번: N-Queen

접근

2가지 방법이 있다: 

- 각 스퀘어를 전부 탐색하며 조건을 찾는다. => n^n 

- 한 행에 하나의 퀸이 온다는 것을 이용해 행별로 탐색 => n (풀이 참조)

 

2번째의 경우가 훨씬 시간복잡도가 줄기 때문에 두 번째 방법으로 간다

즉, 행이나 열 하나를 잡고 그 행에 첫 퀸을 두었을 때 다음 행이나 열을 돌면서 경우의 수를 탐색한다. 

 

풀이

const input = require("fs").readFileSync("/dev/stdin").toString();

const solution = (input) => {
  const N = +input;
  const row = Array(N).fill(0);
  let cnt = 0;

  const isPossible = (x) => {
    for (let i = 0; i < x; i++) {
      if (row[x] === row[i]) return false;
      if (x - i === Math.abs(row[x] - row[i])) return false;
    }
    return true;
  };

  const dfs = (x) => {
    if (x === N) {
      cnt++;
      return;
    }

    for (let y = 0; y < N; y++) {
      row[x] = y; 
      if (isPossible(x)) {
        dfs(x + 1); 
      }
    }
  };

  dfs(0);

  return cnt;
};

console.log(solution(input));