[leetcode] N-Queens

유의할점

대각선일때 경우를 잘생각
vector은 STL아님.

풀이

방문처리를 해줘야하는 부분은 Q이 위치한 column / 왼쪽 대각선 / 오른쪽 대각선이 존재한다.

대각선을 계산할때는 다음과 같이 계산한다.

n=4

왼쪽대각선인경우 y+x

0 1 2 3

1 2 3 4

2 3 4 5

3 4 5 6

오른쪽대각선인경우 n-1-y+x

3 4 5 6

2 3 4 5

1 2 3 4

0 1 2 3

코드

C++

class Solution {
private:
    vector<vector<string>> res;
    vector<string> chessBoard;
    bool col[9];
    bool crossLeft[17];
    bool crossRight[17];
public:
    
    
    void makeNQueens(int n, int y){
        if(n==y){
            res.push_back(chessBoard);
            return;
        }
        string s(n,'.');
        for(int x = 0; x<n; x++){
            if(!col[x]&&!crossLeft[y+x]&&!crossRight[n-1-y+x]){
                col[x] = true;
                crossLeft[y+x] = true;
                crossRight[n-1-y+x] = true;
                s[x] = 'Q';
                chessBoard.push_back(s);
                makeNQueens(n, y+1);
                chessBoard.pop_back();
                s[x] = '.';
                crossRight[n-1-y+x] = false;
                crossLeft[y+x] = false;
                col[x] = false;
            }
        }
        return;
    }
    
    vector<vector<string>> solveNQueens(int n) {
        makeNQueens(n,0);
        return res;
    }
};