BOJ 1799번: 비숍

문제

문제 바로가기> BOJ 1799번: 비숍

1799번: 비숍

 

풀이

문제의 핵심은 "비숍의 이동 방식(체스판의 색깔)" 이다.

비숍은 대각선으로만 이동 가능하고,

이는 이동 전과 이동 후의 체스판의 색깔이 같음을 의미한다.

 

이 부분이 왜 핵심인가!!

그 이유는, 같은 색깔에 있는 비숍끼리만 영향을 끼칠 가능성이 있기 때문!! 이다.

따라서 전체 경우의 수인 2^(N*N)을 한번에 모두 탐색하는 것이 아닌,

검은색, 흰색으로 나누어 2번 탐색 + backtracking 하여,

2(검은색, 흰색) * 2^((N/2)*(N/2))로 시간 복잡도를 줄일 수 있다!!

 

💡 시간 복잡도가 2^(N*(N/2))이 아니라, 2^((N/2)*(N/2)) 인 이유

N=8, map의 모든 곳의 비숍을 놓을 수 있는 경우, 흰색 32칸, 검은색 32칸에 대해서
놓을지, 말지에 대한 경우의 수를 생각해보면, 2^32 + 2^32 이다.

하지만, backtracking을 하므로,
비숍을 놓을 수 없는 지점들에서는 경우의 수를 2가 아닌 1로 생각해 주어야 한다.

비숍을 가능한 최대로 놓았을 때,
비숍을 놓을 수 없는 지점이 항상 상 N x N / 2개이상이 생기고,
이를 검은색과 흰색으로 나누어 탐색하므로 총 N x N / 4칸을 백트래킹 하는 셈이다.

따라서 실제 경우의 수는 2^16 + 2^16이 되는 것이다!

 

#include<iostream>
#include<algorithm>
#include<vector>
#define MAX 101
using namespace std;

struct POS { int y, x; };
vector<POS> pos, bishop;

int N;
int bk = 0, wh = 0;
bool map[MAX][MAX];

void input() {
	cin >> N;

	bool possible;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> possible;
			if (possible) pos.push_back({ i, j });
		}
	}
}

bool impossible() {
	for (int a = 0; a < (int)bishop.size() - 1; a++) {
		for (int b = a + 1; b < (int)bishop.size(); b++) {
			int ay = bishop[a].y, ax = bishop[a].x;
			int by = bishop[b].y, bx = bishop[b].x;
			if (abs(ay - by) == abs(ax - bx)) return true;
		}
	}
	return false;
}

void solution_bk(int cnt, int use) {

	if (impossible()) return;
	if (cnt == (int)pos.size()) {
		bk = max(bk, use);
		return;
	}

	solution_bk(cnt + 1, use);

	int y = pos[cnt].y;
	int x = pos[cnt].x;
	if ((y + x) % 2 == 0) {
		bishop.push_back(pos[cnt]);
		solution_bk(cnt + 1, use + 1);
		bishop.pop_back();
	}
}

void solution_wh(int cnt, int use) {

	if (impossible()) return;
	if (cnt == (int)pos.size()) {
		wh = max(wh, use);
		return;
	}

	solution_wh(cnt + 1, use);

	int y = pos[cnt].y;
	int x = pos[cnt].x;
	if ((y + x) % 2 != 0) {
		bishop.push_back(pos[cnt]);
		solution_wh(cnt + 1, use + 1);
		bishop.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	input();
	solution_bk(0, 0);
	solution_wh(0, 0);
	cout << bk+wh;
}