[JS 백준] 9663. N-Queen

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

9663번: N-Queen

 

백트래킹 및 DFS의 진수라고 할 수 있는 엔퀸이다.

 

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';

const input = require("fs")
  .readFileSync("input.txt")
  .toString()
  .trim()
  .split(" ").map(Number);

let N = input[0];

let dx = [-1,1,-1,1];
let dy = [-1,1,1,-1];

// console.log(N);

let chess = new Array(N).fill(false);

for(let i = 0; i < N; i++){
    chess[i] = new Array(N).fill(false);

    
}

let result = 0;


solution = (box, n, x, y, count) => {
    
    if(count === 8){
        result +=1;
        return
    }

    if(x === n-1 && y===n-1){
        return;
    }
    
    for(let i = 0; i < n; i++){
        for(let j = 0; j < n; j++){
            if(box[i][j] === false){
                if(search(box,i,j,n) === true){

                    box[i][j] = true;
                    solution(box,n, i, j,count+1);
                    box[i][j] = false;
                }
            
        }
    }
}


}

search = (box, i,j,n) => {
    for(let k = 0; k < n;  k++){
        if(box[k][j] === true || box[i][k] === true){
            return false;
        }
    }
    for(let k = 0; k < 4; k++){
        x = dx[k];
        y = dy[k];
        
        while(true){
            x = x+x;
            y = y+y;

            if(x+i<0 || x+i>=n || y+i < 0 || y+i >= n){
                break;
            }

            if(box[x+i][y+i] === true){
                return false;
            }
        }
        
    }
    
    return true;
}
solution(chess, N,0,0,0);

console.log(result);

 

처음에는 이런 방식으로 풀었는데 시간도 오래걸리고 답도 나오지 않았다.

 

그러다 알게된 사실.

 

대각선 경로상에 존재하는 것을 찾는 공식이 있다.

X1 - X2 === Math.abs(Y1 - Y2) 일 경우 대각선에 무언가가 있습니다.

 

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';

const input = require("fs")
.readFileSync("input.txt")
.toString()
.trim()
.split(" ").map(Number);

let N = input[0];
let result = 0;
let chess = new Array(N).fill(0);
// 검색 알고리즘
const check = (dept) =>{
    for(let i =0; i < dept; i++){
        if(chess[i] === chess[dept] || dept - i === Math.abs(chess[i]-chess[dept])){
            return false;
        }
    }
    return true;
}

// DFS 알고리즘

const DFS = (dept) => {

    if(dept === N){
        result += 1;
        return;
    }

    for(let i = 0; i < N; i++){
        chess[dept] = i;
        if(check(dept)){
            DFS(dept+1);
        }
    }

}

DFS(0);

console.log(result);

 

배열을 2차원 배열로 안만들고 1차원 배열로 만들어도 되는 이유는 같은 열에는 올 수 없기 떄문입니다.