[백준 1799] 비숍 (C++)

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

1799번: 비숍

1. 주의할 점

- 처음에 비숍을 안넣는게 최선일 수 있다

- 체스판과 관련된 문제는 흑백으로 나눠서 생각하도록 한다 -> 시간복잡도가 줄어든다

 

2. 구현

- 백색 칸과 흑색 칸을 구분해서 흑색칸일 때 최대 + 백색칸일 때 최대를 구한다

- 해당칸이 비숍을 놓을 수 있는 칸인 경우, 기존에 설치한 비숍의 영역에 포함되는지 확인한다 (X+Y의 합이 같거나 X-Y의 값이 같으면 기존 비숍의 영역에 포함)

- 다음 검색하는 칸은 X+2로 한다 (흑->흑, 백->백)

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int num, result[2];
struct info {
	int x, y;
};
info tmp;
vector<info> v;
int arr[10][10];

void bishop(int y, int x, int cnt, int color) {
	if (x >= num) {
		y += 1;
		if (color == 0) {
			if (y % 2 == 0) x = 0;
			else x = 1;			
		}
		else if (color == 1) {
			if (y % 2 == 0) x = 1;
			else x = 0;
		}
	}
	if (y == num) {
		if (color == 0)		result[0] = max(result[0], cnt);
		else	result[1] = max(result[1], cnt);
		return;
	}
	if (arr[y][x] == 0)		bishop(y, x + 2, cnt, color);
	else {
		bool avail = true;
		for (int i = 0; i < v.size(); i++) {
			int cx = v[i].x;
			int cy = v[i].y;
			if (cx + cy == y + x || cx - x == cy - y) {
				avail = false;
				break;
			}
		}
		if (avail) {
			tmp.x = x;
			tmp.y = y;
			v.push_back(tmp);
			bishop(y, x + 2, cnt + 1, color);
			v.pop_back();
		}
		bishop(y, x + 2, cnt, color);
	}
}

int main() {
	cin >> num;
	int val;
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++) 
			cin >> arr[i][j];	
	bishop(0, 0, 0, 0);
	bishop(0, 1, 0, 1);
	cout << result[0] + result[1];
	system("pause");
	return 0;
}