비숍 1799번 [백준]

비숍 1799번 [백준]

이번에 풀은 문제는 비숍의 특징을 이용하여 체스판을 2개로 쪼개서 계산 복잡도를 초과하지 않는 방법으로 풀어냈습니다.

 

문제을 쪼개지 않고 완전탐색으로 문제을 풀게 될 경우, 서로에게 영향을 끼치므로 정확히는 모르지만 대략 최대 2^100번의 계산을 하게 된다고 볼 수 있습니다.

 

하지만 비숍의 특성상 검정칸에 있는 비숍은 검정칸에만 영향을 끼칠 수 있고, 하얀칸에 있는 비숍은 하얀칸에만 영향을 끼칠 수 있습니다. 

수전증...

아이디어는 칸을 나누는 것입니다. 만약 칸을 검정칸과 하얀칸을 따로 나누어 계산을 하게 된다면 10*10 은 5*5인 칸 2개를 계산하는 것과 같아집니다. 2의 25승은 대략 3000만이므로 요구하는 시간복잡도 10초에는 넉넉하게 들어가겠지요.

 

단순한 backtracking 문제였습니다.

 

ll l[20];//row+col
ll r[20];//n-1 + col-row
vector<vector<ll>> matrix;
ll ans[2];
ll n;


void backtracking(ll row, ll col, ll count, ll color) {
	if (col >= n) {
		row++;
		if (color == 0)col = row % 2;
		if (color == 1)col = (row + 1) % 2;
	}
	if (row >= n) {
		ans[color] = max(ans[color], count);
		return;
	}
	if (matrix[row][col] && !l[row + col] && !r[n - 1 + col - row]) {
		l[row + col] = r[n - 1 + col - row] = 1;
		backtracking(row, col + 2, count + 1, color);
		l[row + col] = r[n - 1 + col - row] = 0;
	}
	backtracking(row, col + 2, count, color);
}

void solve() {
	cin >> n;
	matrix = vector<vector<ll>>(n, vector<ll>(n));
	for (vector<ll>& row : matrix)
		for (ll& element : row)cin >> element;
	backtracking(0, 0, 0, 0);
	backtracking(0, 1, 0, 1);
	cout << ans[0] + ans[1] << endl;
	
}

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