글 읽기 - 1799 비숍 가지를 어떻게 쳐야하나요?

stiti 7년 전 0

백트래킹을 이용해서 풀어보았습니다.

10*10의 배열이 최대의 크기이고

bm[11] 을 이용하여 각 열에 들어가는 값을 저장합니다.

이때는 비트마스크를 이용해서 bm에 저장을 하게 되고

n=10일경우 0~1023까지의 값이 들어가겠죠.

가지치기는 N-QUEEN 풀듯이 각각의 대각선을 조사했습니다.

그리고 모든 열을 채운 경우 또 일일히 비숍의 숫자를 세주었습니다.

결국 10*10의 input을 넣으니 하루종일 계산하고 있습니다......

어떤식으로 가지를 쳐서 시간을 줄일 수 있을까요?

#include <iostream>
#include <string.h>
using namespace std;
int arr[11][11];
int bm[11];
int es[11];
int n;
int result = 0;
bool ispromise(int stage, int now)
{
	cout << stage << ' ' << now << endl;
	memset(es, 0, sizeof(es));
//	int qwerq = now;
	//	cout << stage << ' ' << now << endl;
	int qwer = 1;
	while (now > 0)
	{
		if (now & 1)
			es[qwer] = 1;
		else
			es[qwer] = 0;
		now >>= 1;
		qwer++;
	}
//	if (stage == 1)
//	{
//		cout << "now == " << qwerq << endl;
//		for (int i = 1; i <= n; i++)
//			cout << es[i] << ' ';
//		cout << endl;
//	}
	//now is translated into es[]
	for (int i = 1; i <= n; i++)
	{
		if (es[i] == 1)
		{
			if (arr[stage][i] == 0)
				return false;
			for (int j = 1; j < stage; j++)
			{
				if (i + stage - j <= n)
				{
					if (bm[j] & (1 << i + stage - j - 1))
						return false;
				}
				if (i - stage + j >0)
				{
					if (bm[j] & (1 << i - stage + j - 1))
						return false;
				}
			}
		}
	}
	return true;
}
void go(int stage)
{
//	cout <<"stage "<< stage << endl;
	if (stage > n)
	{
		int kiki =0;
		for (int i = 1; i <= n; i++)
		{
			int temp = bm[i];
			while (temp > 0)
			{
				if (temp & 1)
					kiki++;
				temp >>= 1;
			}
		}
		if (kiki > result)
			result = kiki;
		return;
	}
	for (int i = 0; i < (1 << n); i ++)
	{
//		cout << stage << ' ' << i << ' ' << ispromise(stage, i) << endl;
		if (ispromise(stage, i))
		{
			bm[stage] = i;
			go(stage + 1);
		}
	}
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> arr[i][j];
	go(1);
	cout << result << endl;
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1799 비숍 가지를 어떻게 쳐야하나요?

stiti 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말