[LeetCode] 52. N-Queens II

해당 문제는 이전 문제와 동일하게 백트레킹을 활용하여 풀이하면 된다.

다만, 이 전 문제는 가능한 경우의 수를 2차원 배열로 반환해야 했던 것과 다르게

현재 문제는 경우의 수를 반환해야한다.

😎풀이

function totalNQueens(n: number): number {
    const board = Array.from({ length: n }, () => Array(n).fill('.'))
    let result = 0

    function isValid(row: number, col: number) {
        // 열 검사
        for(let i = 0; i < n; i++) {
            const curCell = board[i][col]
            if(curCell === 'Q') return false
        }

        // 좌측 상향 대각선 검사
        for(let i = row - 1, j = col - 1; i >= 0 && j >= 0; i --, j--) {
            const curCell = board[i][j]
            if(curCell === 'Q') return false
        }

        // 우측 상향 대각선 검사
        for(let i = row - 1, j = col + 1; i >= 0 && j < n; i --, j++) {
            const curCell = board[i][j]
            if(curCell === 'Q') return false
        }

        return true
    }

    function backTracking(row: number) {
        // 끝까지 도달했다면 경우의 수 + 1
        if(row === n) {
            result++
            return
        }

        for(let i = 0; i < n; i++) {
            if(!isValid(row, i)) continue
            board[row][i] = 'Q'
            backTracking(row + 1)
            board[row][i] = '.'
        }
    }

    // 첫 행부터 끝까지 반복
    backTracking(0)

    return result
};