[BOJ] 1799 : 비숍

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

---

백트레킹 완전탐색

● 비숍은 대각선으로 움직이므로  체스판에서 흰색칸 / 검은색칸 으로 나눴을 때, 흰색칸에 있는 비숍은 흰색칸에 있는 비숍들끼리만 영향을 끼치고, 검은색칸에 있는 비숍은 검은색칸에 있는 비숍들끼리만 영향을 끼친다. --> 검은색 칸 / 흰색 칸 으로 나눠서 백트레킹을 각각 진행해주면 복잡도를 줄일 수 있습니다.

● 우리는 체스판의 왼쪽 위(0, 0) 부터 오른쪽 아래(N -1, N -1) 으로 비숍을 세울 수 있으면 세우고, 아니면 넘어가면서 진행할 것이므로 현재 비숍을 세울 수 있는 칸(1) 이면 왼쪽 위 대각선과 오른쪽 위 대각선에 비숍이 있는지 없는지만 체크하고, 왼쪽 아래 / 오른쪽 아래는 아직 비숍을 세우지 않았으므로 체크하지 않아도 됩니다.

#include<iostream>
#include<algorithm>
using namespace std;

int N, map[10][10];
int ansW, ansB;

bool check(int r, int c) {
	int tempR = r, tempC = c;
	while (0 <= tempR && 0 <= tempC) {
		if (map[tempR][tempC] == 2)
			return false;
		tempR--, tempC--;
	}
	tempR = r, tempC = c;
	while (0 <= tempR && tempC < N) {
		if (map[tempR][tempC] == 2)
			return false;
		tempR--, tempC++;
	}
	return true;
}

void Backtracking(int r, int c, int count, bool flag) {
	if (c >= N) {
		r++;
		if (c % 2 == 0) c = 1;
		else c = 0;
	}
	if (r >= N) {
		if (flag) ansW = max(ansW, count);
		else ansB = max(ansB, count);
		return;
	}
	if (map[r][c] == 1 && check(r, c)) {
		map[r][c] = 2;
		Backtracking(r, c + 2, count + 1, flag);
		map[r][c] = 1;
	}
	Backtracking(r, c + 2, count , flag);
}


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];
	Backtracking(0, 0, 0, 0);
	Backtracking(0, 1, 0, 1);
	cout << ansW + ansB << '\n';
	return 0;
}

---