백준 1799번: 비숍 (C++)

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

1799번: 비숍

흑과 백으로 칸을 구분한다.

 

1을 흑 0을 백이라고 하면

 

1 0 1 0

0 1 0 1

1 0 1 0

0 1 0 1

 

이런식으로 체스판이 이루어져있다고 생각하고 흑은 흑대로 먼저 처리하고, 백은 백대로 먼저 처리하는 것이다.

 

개인적으로 굉장히 해내기 어려운 발상이라고 생각한다.

 

#include<iostream>
using namespace std;
int n, m[10][10];
int cnt = 0, Bmax = 0, Wmax = 0;
bool isused1[20], isused2[20];
void Black(int row, int col, int cnt) {
	if (col >= n) {
		row++;
		if (row % 2 == 0) col = 0;
		else
			col = 1;
	}
	if (Bmax < cnt) Bmax = cnt;
	if (row >= n) return;
	
	if (m[row][col] == 1 && !isused1[row + col]
		&& !isused2[row - col + n - 1]) {
		isused1[row + col] = true;
		isused2[row - col + n - 1] = true;
		Black(row, col + 2, cnt + 1); //(r,c)가 가능한 지점일 때
		isused1[row + col] = false;
		isused2[row - col + n - 1] = false;
	}
	Black(row, col + 2, cnt);
}
void White(int row, int col, int cnt) {
	if (col >= n) {
		row++;
		if (row % 2 == 0) col = 1;
		else
			col = 0;
	}
	if (Wmax < cnt) Wmax = cnt;
	if (row >= n) return;

	if (m[row][col] == 1 && !isused1[row + col]
		&& !isused2[row - col + n - 1]) {
		isused1[row + col] = true;
		isused2[row - col + n - 1] = true;
		White(row, col + 2, cnt + 1); //(r,c)가 가능한 지점일 때
		isused1[row + col] = false;
		isused2[row - col + n - 1] = false;
	}
	White(row, col + 2, cnt);
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> m[i][j];
	

	Black(0, 0, 0);
	for (int i = 0; i < 2 * n - 1; i++) {
		isused1[i] = false;
		isused2[i] = false;
	}
	White(0, 1, 0);
	cout << Wmax + Bmax << '\n';
}