[백준 9663번] N-Queen(C++)

 

이런 경우도 마찬가지.

 

이런식으로 완전탐색으로 d를 하나씩 증가시키면서 row가 바뀌고, 이에따라 board의 상태가 바뀐다.

다음 depth에서 놓을 수 있는 위치에 Q를 위치시키고 보드의 상태를 바꾸며, 갈곳이 없으면 return 하고 

위의경우세어 d==4가 되면 d==3위치에까지 Q가 자리했다는 의미이므로 count를 1증가시키고 종료한다.

 

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
int board[16][16];
int cnt = 0;
int N;

void dfs(int d){
    vector<pair<int,int>> toClear;
    
    //종료조건, 보드크기가 0~N-1이니, N까지 들어가면 종료.
    if(d ==N){        
        cnt++;
        return;
    }
    
    
    for(int i = 0 ; i< N;i++)
    {
    	//보드의 0은 갈 수 있는곳, 1은 갈 수 없는곳. 초기상태 모두 0임.
        if(board[d][i] ==0)
        {
            //board setting (can't go)
            //왼쪽 아래, 아래, 오른쪽 아래
            for(int p = 1; p<N-d; p++)
            {
                //바로 아래
                if(board[d+p][i]==0)
                {
                    board[d+p][i] =1;
                    toClear.push_back({d+p,i}); //나중에 클리어할 위치.
                }
                //왼쪽 아래
                if(board[d+p][i-p]==0 && i-p>=0)
                {
                    board[d+p][i-p]=1;
                    toClear.push_back({d+p,i-p});
                }
                //오른쪽 아래
                if(board[d+p][i+p]==0 && i+p<N)
                {
                    board[d+p][i+p]=1;
                    toClear.push_back({d+p,i+p});
                }
            }

            dfs(d+1);
            
            //board clear
            while(!toClear.empty()){
                // 보드 표기해놓은거 다시 복구
                int x,y;
                x = toClear.back().first;
                y = toClear.back().second;
                toClear.pop_back();
                board[x][y] = 0;
            }
        }
    }
    return;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    dfs(0);
    cout << cnt;
}

 

풀고나서 채점현황 봤는데, 시간이 너무 오래걸려서 ㅠ

다른 코드들을 봤는데 1차원 배열로 푸시던데 어떻게 한건지 이해가 잘 안된다..

나중에 다른 블로그에서 좀 찾아보자.