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

혅·2025년 2월 13일

JavaScript

백준, 프로그래머스 -JavaScript-

목록 보기

197/215

문제

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

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

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

제한 사항

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

예제 입력

n: 4

예제 출력

내가 했던 풀이 방법

queen이 n×n board에 n개가 존재하기 위해서는 무조건 한 row에 하나의 queen이 존재해야 한다. 즉, row를 0부터 n-1까지 반복해서 해당 row에서 위치할 수 있는 경우에 queen을 배치하고 다음 row를 체크하는 방식으로 처리한다.

board를 n×n 배열로 선언하고 모든 값을 false로 채워준다.
i를 0부터 n-1 반복한다 여기서 i는 col이 된다. 해당 위치를 기준으로 isValid값이 true라면 해당 위치에 queen을 두어도 된다는 의미이므로 해당 위치를 true로 변경하고 다음 row+1를 체크할 DFS를 호출한다. 재귀가 끝나고 돌아오게 되면 row에서 그 위치가 아닌 다른 위치를 찾아보기 위해 해당 위치를 다시 false로 변경하고 반복한다.
row에는 하나만 존재하도록 DFS를 설계하였으므로 isValid는 3가지를 검사해야 한다. 먼저 같은 col에 위치한 queen이 있을 경우 false를 반환한다. 그 다음 왼쪽 위 대각선 방향에 queen이 존재하는 지 체크해야 한다. 해당 위치를 기준으로 row와 col을 모두 1씩 감소하면 해당 방향을 체크할 수 있다. 마지막으로 오른쪽 위 대각선 방향에 queen이 존재하는 지 체크해야 한다. 이는 row는 기존과 같이 감소하지만 col은 1씩 증가하면 해당 방향을 체크할 수 있다. 이들 경우 중에 true를 반환하는 경우에는 false를 return 한다. 모든 방향 검사를 끝냈을 때 return이 되지 않았다면 queen을 두어도 되므로 true를 반환한다.

코드

function solution(n) {
    var answer = 0;
    let board = Array.from({length: n}, ()=>Array(n).fill(false));
    
    function isValid(col, row) {
        for(let i=0; i<row; i++) {
            if (board[i][col]) return false;
        }
        
        for(let i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if (board[i][j]) return false;
        }
        
        for(let i=row-1, j=col+1; i>=0 && j<n; i--, j++) {
            if (board[i][j]) return false;
        }
        
        return true;
    }
    
    
    function DFS(row) {
        if (row === n) {
            answer++;
            return;
        }
        
        for(let i=0; i<n; i++) {
            if(isValid(i, row)) {
                board[row][i] = true;
                DFS(row+1);
                board[row][i] = false;
            }
        }
    }
    
    DFS(0);
    return answer;
}