[기출 상] E-Queen - 백트래킹

[문제]

nqueen 문제의 변형으로 절대 놓을 수 없는 k개의 위치 정보가 추가로 주어질 때의 queen이 서로 공격할 수 없게 배치할 수 있는 경우의 수가 최대 몇 개인지를 리턴한다.

 

[코드]

#include <iostream>

using namespace std;

int col[16]; 
bool xy[14][14] = {false, };
int n, result;

bool check(int level)
{
    for (int i = 0; i < level; i++)
        if (col[i] == col[level] || abs(col[level] - col[i]) == level - i) 
            return false;
    //col[i]: x좌표, i: y좌표. (x, y)와 (a, b)에 대해서 두 좌표가 대각선에 위치한다면 a-x == b-y. 
    return true;
}

void nqueen(int row)
{
    if (row == n)
        result++; // n번째 퀸을 놓으면 경우의 수 증가
    else
    {
        for (int i = 0; i < n; i++)
        {
          col[row] = i;
					if(xy[row][i]) //불가능한 곳에 놓으면 패스.
						continue;
          if (check(row))
              nqueen(row + 1);
        }
    }
}

int main() {
  cin >> n;
	int k;
	int x[14];
	int y[14];
	cin >> k;
	for(int i=0; i<k; i++){
		cin >> x[i];
	}
	for(int i=0; i<k; i++){
		cin >> y[i];
	}
	
	for(int i=0; i<k; i++){
		xy[x[i]-1][y[i]-1] = true;
	}
	
	
  nqueen(0);
  std::cout << result;
}