백준 9663 N-Queen / C++

문제 : 9663

풀이 point

백트래킹 문제
퀸을 둘 수 있는 자리를 visit 배열 3개로 관리(세로-열, 대각선 위, 대각선 아래
for문은 세로를 함수의 인자는 가로를 늘리면서 진행

풀이 순서

백트래킹 구현
visit 배열 3개를 씀에 유의
undefined

코드

//백준 9663, N-Queen

#include <iostream>
#include <vector>
#include <queue>

int N;
bool height[100];
bool diagup[100];
bool diagdown[100];
int cnt{0};

void solve(int k){
    if(k == N){
        ++cnt;
        return;
    }
    
    for(int i{0}; i<N; ++i){
        if(!height[i] && !diagup[i+k] && !diagdown[k-i+N-1]){
            height[i] = true;
            diagup[i+k] = true;
            diagdown[k-i+N-1] = true;
            solve(k+1);
            height[i] = false;
            diagup[i+k] = false;
            diagdown[k-i+N-1] = false;
        }
    }
}

int main(){
    std::cin >> N;
    solve(0);
    std::cout << cnt;
    return 0;
}