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

이 글은 @longroadhome님의 게시글을 참고하여 풀이된 글 입니다.

🧡문제 설명

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

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

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

---

💛제한사항

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

---

💚입출력 예

n	result
4	2

---

💙입출력 예 설명

입출력 예 #1

• 문제의 예시와 같습니다.

---

💜나의 풀이

function solution(n) {
    // 조건에 만족하도록 배치할 수 있는 경우의 수
    let result = 0
    // dfs알고리즘
    function dfs(board, row) {
        // 마지막 행까지 도달한 경우 경우의 수 ++
        if(row === n) result++
        else {
            for(let i = 1 ; i <= n ; i ++) {
                // 다음 행에 수를 추가하고 유효값인지 검사
                board[row+1] = i
                if(isValid(board, row+1)) dfs(board, row+1)
            }
        }
    }
    // 퀸의 위치가 유효한지 검사
    function isValid(board, row) {
        for(let i = 1 ; i < row ; i ++) {
            // 퀸끼리 번호가 겹친다면 false 반환
            if(board[i] === board[row]) return false
            // 퀸끼리 기울기가 같다면 같은 대각선 경로에 있는것이기 때문에 false 반환
            if(Math.abs(board[i] - board[row]) === Math.abs(i-row)) return false
        }
        return true
    }
    for(let i = 1 ; i <= n ; i ++) {
        // 편의를 위해 배열을 1부터 시작하도록 n+1의 길이의 배열 생성
        const board = new Array(n+1).fill()
        board[1] = i
        dfs(board, 1)
    }
    
    return result
}