[LeetCode # 52] N-Queens II

N-Queens (https://ggop-n.tistory.com/34) 문제와 유사하지만, 앞선 문제에서 N 개의 Queen 을 배치한 체스판을 결과로 return 하는 게 아닌, N 개의 Queen 을 배치한 체스판이 몇 개의 모양으로 존재할 수 있는 지를 구하는 문제

 

N-Queens 문제 풀이와 풀이 방식은 동일하게 진행했고, 차이가 있었던 점은 결과값으로 몇 개의 경우가 존재하는 지만 저장하도록 했다.

 

작성한 코드는 다음과 같다.

 

class Solution {
public:
    int ans;
    bool check(vector<vector<bool>>& board, int r, int c, int n) {
        for (int k = 1; r - k >= 0; k++) {
            if (board[r - k][c])
                return false;
            if (c - k >= 0 && board[r - k][c - k])
                return false;
            if (c + k < n && board[r - k][c + k])
                return false;
        }
        return true;
    }
    void solveNQueen(vector<vector<bool>>& board, int row, int n) {
        if (row == n) {
            ans++;
            return;
        }
        for (int j = 0; j < n; j++) {
            if (check(board, row, j, n)) {
                board[row][j] = true;
                solveNQueen(board, row + 1, n);
                board[row][j] = false;
            }
        }
    }
    int totalNQueens(int n) {
        vector<vector<bool>> board(n, vector<bool>(n, false));
        solveNQueen(board, 0, n);
        return ans;
    }
};