프로그래머스 N-Queen javascript

프로그래머스

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

경우의 수

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

예제 1번을 그림으로 체크해 봤을 때

퀸은 가로 세로 대각선 전부 다른 퀸이 존재 할 수 없으므로

1. 가로든 세로든 한줄에 하나만 위치한다.

2. 가로나 세로는 1차 배열에 넣은 index로 확인이 가능하다.

3. 대각선은 왼쪽으로 갈 경우  (x-dx) === -(y-dy) , 오른쪽 대각선인 경우 (x-dx) === (y-dy)

 

 

 

function solution(n) {
    var answer = 0;
    const visited = new Array(n).fill(false);
    const checker = (v,arr) =>{
        for(let i = 0 ; i < arr.length; i++){
        	// 가로나 세로는 1차 배열에 넣은 index로 확인이 가능하다.
            const [x,y] = [i,arr[i]];
            const [dx,dy] = [arr.length,v];
            // 대각선은 왼쪽으로 갈 경우  (x-dx) === -(y-dy) , 
            // 오른쪽 대각선인 경우 (x-dx) === (y-dy)
            if((dx-x) === (dy-y) || (dx-x) === (y-dy)){
                return false;
            }
        }
        return true;
    }
    const dfs = (arr=[]) =>{
        if(arr.length === n){
            answer++;
            return;
        }
        // 가로든 세로든 한줄에 하나만 위치한다.
        for(let i = 0 ; i < n ; i++){
            if(visited[i] === true) continue;
            if(checker(i,arr) === false) continue;
            visited[i] = true;
            arr.push(i);
            dfs(arr)
            visited[i] = false;
            arr.pop();
        }
    }
    dfs()
    return answer;
}