[LeetCode] 51. N-Queens

백트레킹의 대표적인 문제인 N-Queens 이다.

행을 기준으로 각 열에 퀸을 배치하여 가능한 모든 경우의 수를 파악하고 정답 배열에 추가하였음

😎풀이

function solveNQueens(n: number): string[][] {
    const board = Array.from({ length: n }, () => Array(n).fill('.'))
    const result = [];

    // 퀸을 놓을 수 있는지 확인하는 함수
    function isValid(row: number, col: number): boolean {
        // 같은 열에 퀸이 있는지 확인
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
        }

        // 왼쪽 위 대각선 확인
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }

        // 오른쪽 위 대각선 확인
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') return false;
        }

        return true;
    }

    // 백트래킹 함수
    function backtrack(row: number): void {
        if (row === n) {
            // 모든 행에 퀸을 배치했으면 결과에 추가
            result.push(board.map(row => row.join('')));
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isValid(row, col)) {
                board[row][col] = 'Q';  // 퀸 배치
                backtrack(row + 1);     // 다음 행으로 이동
                board[row][col] = '.';  // 백트래킹: 퀸 제거
            }
        }
    }

    backtrack(0);  // 첫 번째 행부터 시작
    return result;
}