1799 - 비숍

첫번째 풀이

#include<iostream>
#include <map>
#include <queue>
using namespace std;

bool l_visited[50]; // 왼쪽아래로 가는 대각선
bool r_visited[50]; // 오른쪽 아래로 가는 대각선
int arr[11][11];
int N;
int ans;
map < int, int > m;

void func(int x, int y, int cnt) {
	if (ans < cnt) {
		ans = cnt;
	}
	for (int i = x; i <= N; i++) {
		for (int j = y; j <= N; j++) {
			if (arr[i][j] == 0) { continue; }
			if (l_visited[i + j] == 1) { continue; }
			if (r_visited[i - j + 10] == 1) { continue; }
				l_visited[i + j] = 1;
				r_visited[i - j + 10] = 1;
				cnt++;
				func(i, j, cnt);
				l_visited[i + j] = 0;
				r_visited[i - j + 10] = 0;
				cnt--;
		}
		y = 1;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];
		}
	}
	func(0, 0, 0);

	cout << ans;
	return 0;
}

시간초과!
N-Queens 문제처럼 백트래킹을 시도하면 시간초과가 난다 N-Queens에서는 임의의 행에 퀸 하나를 놓았다면, 그 행의 다른 열에 대해서는 검사를 하지 않았기에 가능하였다.

하지만, 비숍 문제에서는 모든 곳에 비숍을 놓을 수 있다면
n이 10일 경우 2^(10x10)(모든 칸에 놓을 경우 놓지 않을 경우가 칸마다 발생)하므로 N-Queens문제 처럼 풀기 불가능하다.

두번째 풀이

#include<iostream>
#include <map>
#include <queue>
using namespace std;

bool l_visited[50]; // 왼쪽아래로 가는 대각선
bool r_visited[50]; // 오른쪽 아래로 가는 대각선
int arr[11][11];
int N;
int ans;
int bishop[2];

void func(int x, int y, int cnt, int color) {
	if (x>N) {
		if (bishop[color] < cnt) { // 최댓값 갱신
			bishop[color] = cnt;
		}
		return;
	}
	if (y > N) {
		x++;
		if (y % 2 == 1) y = 2; // 홀수면 짝수로 바꿔주기
		else y = 1; // 짝수면 홀수로 바꿔주기
	}
	//말을 놓을 수 있을 때
	if (arr[x][y] && !l_visited[x + y] && !r_visited[x - y + 10]) {
		l_visited[x + y] = 1;
		r_visited[x - y + 10] = 1;
		func(x, y+2, cnt+1, color); // 말을 놓는 경우
		l_visited[x + y] = 0;
		r_visited[x - y + 10] = 0;
	}
	func(x, y+2, cnt, color); // 말을 안놓는 경우
	// *말을 놓을수 있을 때도 안 놓는 경우도 계산 해야 함
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];
		}
	}
	func(1, 1, 0, 0); // 검정
	func(1, 2, 0, 1); // 흰색

	
	cout << bishop[0] + bishop[1];
	
	return 0;
}

체스판을 생각해보면 서로다른 비숍이 검정칸과 흰색칸에 있을 때 서로 영향을 받지 않으므로
검정 칸과 흰색 칸을 두개로 쪼개어 계산해주면 2*2^(5x5)의 시간 복잡도로 계산이 가능하다