(9663) N-Queen

https://www.acmicpc.net/problem/9663

단계별로 풀어보기

20단계(백트래킹) 5번째

 

 

 

꽤나 어려운 백트래킹 문제

n*n 체스판에 대응되는 벡터를 만든 뒤, 한 줄씩 백트래킹으로 체크한다.

놓을 수 없다면 패스하고, 놓을 수 있다면 아래쪽 직선 및 대각선으로 퀸의 범위의 체스판에 놓을 수 없다고 체크한다.

(한 줄씩 내려오며 훑기 때문에 자신의 자리를 포함한 같은 줄 및 위쪽 줄은 체크할 필요가 없다.)

이때 한 칸이 여러 퀸에 의해 막힐 수 있으므로 bool이 아닌 정수형 변수를 사용해야 한다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, ans= 0;
  
  cin >> n;
  
  vector v(n, vector<short> (n));
  
  auto func= [&](auto self, int depth) -> void {
    if(depth==n){
      ans++;
      return;
    }
    
    for(int i=0;i<n;i++){
      if(v[depth][i])  continue;
      
      for(int j=depth+1;j<n;j++){
        v[j][i]++;
        if(i+depth-j>=0)  v[j][i+depth-j]++;
        if(i-depth+j<=n-1)  v[j][i-depth+j]++;
      }
      self(self, depth+1);
      for(int j=depth+1;j<n;j++){
        v[j][i]--;
        if(i+depth-j>=0)  v[j][i+depth-j]--;
        if(i-depth+j<=n-1)  v[j][i-depth+j]--;
      }
    }
  };
  
  func(func, 0);
  
  cout << ans;
  
  return 0;
}