Node.js) 백준 9663번 : N-Queen ★

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

9663번: N-Queen

 

백트래킹의 대표문제 N-queen 

dfs 다시 공부하고 돌아와서 풀어보기.

 

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



function solve(n) {
  let answer = 0; 
  let cols = Array(n).fill(0); 
  answer = dfs(n,cols,0,answer); 

  function dfs(n,cols,row,answer){ 
      if(n===row) return ++answer; 
      for(let i =0; i<n; i++){ 
          cols[row] = i; 
          if(isPossible(row,i,cols)){ 
              answer = dfs(n,cols,row+1,answer); 
          }
      }
      return answer; 
  }

  function isPossible(x,y,cols){ 
      for(let i = 0; i<x; i++){ 
          if(cols[i] ===y ||Math.abs(x-i) === Math.abs(y-cols[i]))
          return false; 
      }
      return true; 
  }
return answer;
}

console.log(solve(+input))