백준(BOJ) 1799 비숍 **

# 백트래킹

실제 체스경기를 생각해봤을 때, 흑색칸과 백색칸을 나눠서 계산해야 시간을 통과할 수 있다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 10005
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int n,ans=0,ret=0;
int arr[15][15];
bool tf[25];
vector<pi> v[25],tmp;

void fun(int in)
{
    if(in>n*2-1)
        return;
    if(v[in].size()==0)
    {
        fun(in+2);
        return;
    }
    for(int i=0;i<v[in].size();i++)
    {
        int line=v[in][i].first-v[in][i].second+10;
        if(tf[line]==false)
        {
            
            tmp.push_back(v[in][i]);
            tf[line]=true;
            ans=max(ans,(int)tmp.size());
            fun(in+2);
            tmp.pop_back();
            tf[line]=false;
        }
        else
            fun(in+2);
    }
}

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&arr[i][j]);
    
    int x=1,y=1;
    for(int i=1;i<=n*2-1;i++)
    {
        int cx=x,cy=y;
        while(1<=cx&&cx<=n&&1<=cy&&cy<=n)
        {
            if(arr[cy][cx]==1)
                v[i].push_back(make_pair(cy, cx));
            cx++,cy--;
        }
        i<n?y++:x++;
    }
    
    for(int i=1;i<=2;i++)
    {
        ans=0;
        fun(i);
        ret+=ans;
    }
    printf("%d",ret);
    return 0;
}