[BOJ] 1799_비숍 with cpp

# 생각

두 방향의 대각선을 확인하며 탐색하는 방법으로는 시간 초과가 발생한다 // 2^(10*10)

비숍은 흑과 백으로 나누어져 흑이면 흑 백이면 백으로만 이동가능하므로 다른 색에는 영향을 주지 않는다

때문에, 흑과 백 두가지의 경우로 나누어 풀면 시간을 줄일 수 있다 // 2^(5*5)

 

9663_N-Queen를 활용하여

column - row +  N  - 1을 통해 ( 인덱스가 음수가 되는 것을 방지 하기 위해 N-1을 더해준다 )

대각선에 포함된 칸의 정보들을 저장해준다

 

 

# 전체 코드

// 10s, 128MB
// 10 * 10
#include <bits/stdc++.h>
using namespace std;

int n, ans[2];
vector<pair<int, int>> vStart[2][20];	// [흑,백][\방향 대각선에 포함된 칸]
bool bUsed[2][20];

void dfs(int depth, int cnt, int colour)
{
	if (depth == 2 * n)
	{
		ans[colour] = max(ans[colour], cnt);	// 비숍의 최대 개수
		return;
	}
	for (auto& i : vStart[colour][depth])
	{
		int x, y;
		tie(x, y) = i;
		if (bUsed[colour][x + y]) continue;
		bUsed[colour][x + y] = true;
		dfs(depth + 1, cnt + 1, colour);
		bUsed[colour][x + y] = false;
	}
	dfs(depth + 1, cnt, colour);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int graph;
			cin >> graph;
			if (graph) vStart[(i + j + 1) % 2][i - j + n - 1].push_back({ i,j });
		}
	}
	dfs(0, 0, 0);
	dfs(0, 0, 1);
	cout << ans[0] + ans[1];
}

 

---