N-Queen

문제 설명

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

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

제한 사항

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

입출력 예

n = 4
result = 2

문제 풀이

function solution(n) {
    var answer = 0;
    // 1차원 배열로 행 저장 
    var arr = new Array(n).fill(-1)

    // 재귀를 통해 dfs 탐색
   const dfs = (col, arr) => {
        // 행 탐색을 마쳤을 경우 즉 모든 퀸을 놓을 수 있는 경우 값 추가
       if (col === n) {
           answer++
       }
       var temp = [...arr]

       for (var row = 0; row < n; row++) {
        // 현재 행에 열 위치 저장하기 위한 반복 및 재귀호출
            if (isValid(col, row, temp)) {
                temp[col] = row
                dfs(col + 1, [...temp])
            }
        }

     }
    // 가로, 대각선에 말이 존재하면 false 반환
    const isValid = (col, row, arr) => {
       for (var i = 0; i < col; i++) {
           // 이미 같은 열에 존재하면
           if (arr[i] === row) return false

           if(Math.abs(col - i) === Math.abs(row - arr[i])) return false;
       }
        return true

            // 대각선 상에 존재할 경우
    }
    dfs(0, arr)
    return answer;
}

아이디어 / 접근법

가로, 세로, 대각선에 이미 말이 존재하는 지 판별하고 백트래킹을 이용하여 문제를 푸는 유명한 N-Queen 문제..

후기

대각선 판별이 조금 어려웠던 것 같고 굳이 2차원 배열로 탐색을 안해도 되는 문제였는데 좀 오래걸린 것 같음