[프로그래머스] Lv2. N-Queen - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - N-Queen

문제

제한사항

📌 내가 생각한 풀이

2차원 배열을 사용하지말고, 1차원 배열을 사용하여 공간복잡도를 줄여주자. 그 다음 DFS를 사용하여 다음 depth로 넘어갈때 가능한 경우의 수인지 판단하고 가능하면 넘어가고 불가능하면 종료해주자. 즉 DFS+백트래킹 방법을 사용하여 문제를 해결하자.

const check = (board, depth) =>{
    for(var i =0; i<depth; i++){
        if(board[depth] === board[i]) return false;
        if(Math.abs(board[depth]-board[i]) === Math.abs(depth-i))return false;
    }
    return true;
}

function solution(n) {
    var answer = 0;
    const re = (board, depth) =>{
        if(depth === n-1) answer++;
        else{
            for(var i =0; i<n; i++){
                let next = depth+1;
                board[next] = i;
                if(check(board,next)) {
                    
                    re(board, next)
                }
            }
        }
    }
    for(var i = 0; i<n; i++){
        let board = new Array(n).fill('X');
        board[0] = i;
        re(board, 0);
    }
    return (answer)
}

📌 느낀점

마지막 테스트케이스가 계속 시간초과가 떴다. 인터넷의 자료를 찾아보니 N-Queen 문제는 유명했고 1차원 배열로 줄여주어 공간복잡도를 줄였다.