Boj 1799) 비숍

문제

백준 1799

설명

체스판에 존재하는 대각선 줄은 2N-1 개가 된다. 대각선 축은 우상방향 우하방향 두개가 있어 한 축을 기준으로 잡아서 잡아서 백트래킹을 돌리면 된다. 이때 시간복잡도가 기하급수적으로 커지는데, 백판/흑판은 비숍에 있어 서로 잡을 수 없다는 것을 생각하면 MITM 을 떠올릴 수 있다.

시간 복잡도

O(\(1^2 * 3^2 *...(N-2)^2*N + 2^2 * 4^2 ...(N-3)^2 * (N-1)\))

• \(N\) 이 짝수라고 할때의 시간복잡도로 홀수도 비슷하게 구할 수 있다.

코드

int arr[101], n, visits[21];
int cnt, ans;

void Find(int cur = 0)
{
	if (cur >= (n<<1)-1)
	{
		ans = max(cnt, ans);
		return;
	}

	// 같은 우상 대각선 하에 있는 모든 경우를 탐색
	for (int x = max(0, cur-n+1), y = min(cur,n-1); y >= 0 && x < n; x++, y--)
	{	
		if (!arr[y * n + x] || visits[y-x+n] ) Find(cur + 2);
		else {
			visits[y - x + n] = true; // 우하 대각선에 대해서 방문체크
			cnt++;
			Find(cur + 2);
			cnt--;
			visits[y - x + n] = false;
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n * n; i++) cin >> arr[i];
	int res = 0;
	Find(); res += ans; ans = 0;
	Find(1); res += ans;
	cout << res;
}