[PS] 비숍 / C++ (백준 1799번)

비숍 (백준 1799번)

 

N-Queen 문제와 동일하게 백트래킹으로 해결해야 하는 문제지만 런타임을 더 줄여야 한다.

모든 경우의 수를 탐색하면, k를 nxn 체스판에서 최대로 들어갈 수 있는 비숍의 개수라 놓고 시간 복잡도가 $O(2^k)$가 나올 것이라 예상했다. 10x10 체스판에 최대로 놓을 수 있는 비숍의 수(k)가 18개라 $2^{18}$은 10억을 넘지 않기 때문에 10초 안에 풀 수 있을 것 같았지만 발상 오류였다. 실제론 $O(2^{n*n})$

 

풀이 과정

결국 정해를 찾아보고 문제를 해결했다. 시간을 줄일 수 있는 방법은 $n$x$n$ 체스판을 흑, 백 2개의 $(n/2)$x$(n/2)$ 체스판으로 분할하여 각각 백트래킹을 수행하여 구한 최대로 놓을 수 있는 비숍의 개수를 합치는 것이었다. 이렇게 되면 각 백트래킹에서 $O(2^{(n/2)*(n/2)})$의 시간 복잡도가 소요되며 최대 n값인 10이 들어가도 $2^{25}$은 10억(≒$2^{30}$)을 넘지 않기 때문에 시간 안에 AC를 받을 수 있다.

본인은 다음 비숍이 올 수 있는 자리를 찾을 때, find_next() 함수를 호출하게끔 코드를 짜놓아서, 이 부분만 수정하였다.

 

이전 find_next() 함수 (시간 초과)

pair<int, int> find_next(int x, int y)
{
	while (1) {
		if (x + 1 > n) { y++; x = 1; }
		else x++;
		if (y > n)break;
		if (atk[y][x] == 0 && bi[y][x])
			return make_pair(x, y);
	}
	return make_pair(-1, -1);
}

 

AC 코드(흑, 백 체스판 분리)

#include<iostream>
#include<algorithm>
using namespace std;

int n, dap = 0, white = 0, black = 0;
int bi[11][11], atk[11][11];

pair<int, int> find_next(int x, int y)
{
	while (1) {
		if (x + 2 > n) { y++; x = x % 2 == 0 ? 1 : 2; }
		else x += 2;
		if (y > n)break;
		if (atk[y][x] == 0 && bi[y][x])
			return make_pair(x, y);
	}
	return make_pair(-1, -1);
}

void attack_execute(int x, int y)
{
	for (int i = 1; i + y <= n && i + x <= n; i++)
		atk[i + y][i + x]++;
	for (int i = 1; i + y <= n && x - i > 0; i++)
		atk[i + y][x - i]++;

	return;
}

void attack_release(int x, int y)
{
	for (int i = 1; i + y <= n && i + x <= n; i++)
		atk[i + y][i + x]--;
	for (int i = 1; i + y <= n && x - i > 0; i++)
		atk[i + y][x - i]--;

	return;
}

void f(int x, int y, int count)
{
	if (dap < count + 1)dap = count + 1;
	attack_execute(x, y);
	pair<int, int> next = find_next(x, y);
	if (next.first != -1)
		f(next.first, next.second, count + 1);
	attack_release(x, y);

	next = find_next(x, y);
	if (next.first == -1) return;
	f(next.first, next.second, count);

	return ;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)scanf("%d", &bi[i][j]);
	}
	pair<int, int> next = find_next(-1, 1); // 백 체스판 (1로 시작)
	if (next.first != -1)f(next.first, next.second, 0);
	white = dap;
	dap = 0;
	next = find_next(0, 1); // 흑 체스판 (2로 시작)
	if (next.first != -1)f(next.first, next.second, 0);
    black = dap;
	printf("%d\n", white + black);
	return 0;
}