백준 소스코드 [C++] 1799 비숍

www.acmicpc.net/problem/1799

1799번: 비숍

백준 소스코드 [C++] 1799 비숍

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;

int n;
int arr[12][12];
bool visited[12][12];
vector <pii> color[2];
int res[2];
bool chk(int y, int x) {
	int Y = y, X = x;
	while (1 <= Y && 1 <= X) if (visited[Y--][X--] == true) return false;
	Y = y, X = x;
	while (1 <= Y && X <= n) if (visited[Y--][X++] == true) return false;
	return true;
}

void dfs(int cnt, vector<pii> &v,int k,int sum) {
	for(int i=cnt;i<v.size();i++)
		if (chk(v[i].first,v[i].second) == true) {
			visited[v[i].first][v[i].second] = true;
			res[k] = max(res[k], sum+1);
			dfs(i + 1, v, k,sum+1);
			visited[v[i].first][v[i].second] = false;
		}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 1;i <= n;i++)for (int j = 1;j <= n;j++) {
		cin >> arr[i][j];
		if (arr[i][j] == 1) color[(i + j) % 2].push_back({ i, j });
	}

	dfs(0, color[0],0,0);
	dfs(0, color[1],1,0);
	cout << res[0] + res[1];
	return 0;
}