N-Queens

리트코드에서 꽤 유명한 문제 중 하나인 N-Queens 문제를 풀어보았다.예전에 이 문제를 봤을때는 Hard 난이도를 보고 일찍 포기했지만 왠일인지 좀 문제를 풀고 싶은 마음이 들었다. 읽자마자 이 문제는 모든 경우의 수를 탐색해야 하는 Backtracking 문제라는걸 느꼈고 그대로 실행에 옮겼다. 결국 퀸이 놓이는 어느 조건에서 다른 곳에 넣지 못하게 설정을 해놔야하는데 처음에는 visited 를 bool 로 했다가 틀렸다.

한 경우의 수가 실패한다면 전 단계로 돌아오는 로직인데 돌아오는 과정에서 다시 visited를 일부 초기화 하다보니 위치가 좀 꼬여서 즉석으로 생각한게 +1 -1로직이었고 성공했다. 실력이 많이 죽은 줄 알았는데 그래도 괜찮은거같다.

class Solution {
    vector<pair<int,int>> dir = {{1,0},{1,1},{1,-1}}; 
void changePath(vector<vector<int>>& visited, int index, int i, bool makeTrue){
    int N = visited.size(); 
    int tmpX = index, tmpY = i; 
    for(int i = 0; i < N; i++){
        tmpX += dir[0].first;
        tmpY += dir[0].second; 
        
        if(tmpX < 0 || tmpX >= N || tmpY < 0 || tmpY >= N) continue;
        
        if(makeTrue) visited[tmpX][tmpY] += 1;
        if(!makeTrue) visited[tmpX][tmpY] -= 1; 
    }
    tmpX = index, tmpY = i; 
    for(int i = 0; i < N; i++){
        tmpX += dir[1].first;
        tmpY += dir[1].second; 
        
        if(tmpX < 0 || tmpX >= N || tmpY < 0 || tmpY >= N) continue;
        
        if(makeTrue) visited[tmpX][tmpY] += 1;
        if(!makeTrue) visited[tmpX][tmpY] -= 1; 
    }
    tmpX = index, tmpY = i; 
    for(int i = 0; i < N; i++){
        tmpX += dir[2].first;
        tmpY += dir[2].second; 
        
        if(tmpX < 0 || tmpX >= N || tmpY < 0 || tmpY >= N) continue;
        
        if(makeTrue) visited[tmpX][tmpY] += 1;
        if(!makeTrue) visited[tmpX][tmpY] -= 1; 
    }
}
public:
    void dfs(vector<vector<string>>& board, vector<vector<int>>& visited, int index, vector<vector<string>>& answer){
        if(index >= board.size()){
            vector<string> tmp; 
            for(vector<string>& v : board){
                string t = ""; 
                for(string& s : v){
                    if(s != "Q") t += '.';
                    else t += 'Q'; 
                }
                tmp.push_back(t); 
            }
            answer.push_back(tmp); 
            return; 
        }

        for(int i = 0; i < board[0].size(); i++){
            if(!visited[index][i]){
                visited[index][i] += 1; 
                board[index][i] = 'Q'; 
                changePath(visited,index,i,true); 
                dfs(board,visited,index+1,answer); 
                visited[index][i] -= 1; 
                board[index][i] = '.'; 
                changePath(visited,index,i,false); 
            }
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> answer; 
        string s(1,'.'); 
        vector<vector<string>> board(n,vector<string>(n,s)); 
        vector<vector<int>> visited(n,vector<int>(n,0)); 
        
        dfs(board,visited,0,answer); 
        
        return answer; 
    };
};

배운점:
1. Backtracking
2. 경우의 수 탐색