[BOJ / 백트래킹] 1799 비숍

https://www.acmicpc.net/problem/1799

1799번: 비숍

 

1799 비숍

알고리즘 : DFS, 백트래킹, 아이디어

일반적인 백트래킹을 사용하면 시간초과를 겪게되고, 그리디로 풀면 무수한 틀렸습니다를 주는 문제이다. 체스판의 검은 판과 하얀 판에 있는 비숍끼리는 절대 만날 수 없다는 걸 전제로 두어 나눠서 계산하면 시간 초과를 벗어날 수 있다. 비숍을 둘 때 현 대각선에 비숍을 놓은 적이 있는 지를 O(1)에 확인하기 위해서 xCnt, yCnt를 이용하여 대각선에 두었는지를 확인하였다.

이 경우에 배열이 MAX * 2개 필요한데 이것을 고려하지 않아 시간이 오래 걸렸다. 

홀수와 짝수 판의 경우에 처리해야하는 방법이 다르므로 유의하며 코드를 작성하면 된다. 

 

 

- 반례 -

4

0 1 0 0

1 0 1 0

0 0 0 0

0 0 0 0

2

 

7
0 0 1 0 1 1 0
0 1 1 1 0 0 1
0 0 0 0 1 1 1
0 1 1 0 0 1 1
1 1 1 0 1 0 1
1 0 1 1 0 1 0
1 1 1 1 1 1 1
11

 

 

 

< CODE >

#include <iostream>

using namespace std;

#define MAX 10

int n;

int xCnt[MAX * 2 + 2];
int yCnt[MAX * 2 + 2];

int pan[MAX + 2][MAX + 2];

int xCntNum[MAX + 2][MAX + 2];
int yCntNum[MAX + 2][MAX + 2];

int result = 0;

void init() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			xCntNum[i][j] = i + j - 2;
			yCntNum[i][j] = n - (i - j) - 1;
		}
	}
}

int dfs(int y, int x, int amount) {
	int ret = amount;
	int& xP = xCnt[xCntNum[y][x]];
	int& yP = yCnt[yCntNum[y][x]];

	bool possible = pan[y][x] == 1 && xP == 0 && yP == 0;

	if (possible){
		xP++; yP++;

		ret = max(ret, amount + 1);

		if (x + 2 <= n)
			ret = max(ret, dfs(y, x + 2, amount + 1));
		else if (y + 1 <= n && x == n)
			ret = max(ret, dfs(y + 1, ((n % 2) == 1 ? 2 : 1), amount + 1));
		else if (y + 1 <= n)
			ret = max(ret, dfs(y + 1, ((n % 2) == 1 ? 1 : 2), amount + 1));

		xP--; yP--;
	}

	if (x + 2 <= n)
		ret = max(ret, dfs(y, x + 2, amount));
	else if (y + 1 <= n && x == n)
		ret = max(ret, dfs(y + 1, ((n % 2) == 1 ? 2 : 1), amount));
	else if (y + 1 <= n)
		ret = max(ret, dfs(y + 1, ((n % 2) == 1 ? 1 : 2), amount));

	return ret;
}

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> pan[i][j];
		}
	}

	init();

	result = dfs(1, 1, 0);
	result += dfs(1, 2, 0);

	cout << result;

	return 0;
}

시간 : 24ms

 

------------------------------------------------------------------------------------------

여담 : 모든 케이스가 잘 되는데 틀렸습니다를 발산해서 반례를 찾고자 정답코드와 output을 대조하는 랜덤케이스를 만들었다..

배열 크기가 문제였다.. 반례를 정말 못 찾겠을 때 이 방법을 사용하자.. (정신 건강에 이롭다)

대회에서도 대조는 아니더라도 랜덤케이스를 만드는 방법으로 반례를 검증할 수 있다.

 

#include <iostream>
#include <ctime>
#include <random>
#include <cstdlib>

using namespace std;

#define MAX 10

int n;

int xCnt[MAX * 2 + 1];
int yCnt[MAX * 2 + 1];

int pan[MAX + 2][MAX + 2];

int xCntNum[MAX + 2][MAX + 2];
int yCntNum[MAX + 2][MAX + 2];

int result = 0;



int dfs(int y, int x, int amount) {
	int ret = amount;
	int& xP = xCnt[xCntNum[y][x]];
	int& yP = yCnt[yCntNum[y][x]];

	bool possible = pan[y][x] == 1 && xP == 0 && yP == 0;

	if (possible) {
		xP = 1, yP = 1;

		ret = max(ret, amount + 1);

		if (x + 2 <= n)
			ret = max(ret, dfs(y, x + 2, amount + 1));
		else if (y + 1 <= n && x == n)
			ret = max(ret, dfs(y + 1, ((n % 2) == 1 ? 2 : 1), amount + 1));
		else if (y + 1 <= n)
			ret = max(ret, dfs(y + 1, ((n % 2) == 1 ? 1 : 2), amount + 1));

		xP = 0, yP = 0;
	}

	if (x + 2 <= n)
		ret = max(ret, dfs(y, x + 2, amount));
	else if (y + 1 <= n && x == n)
		ret = max(ret, dfs(y + 1, ((n % 2) == 1 ? 2 : 1), amount));
	else if (y + 1 <= n)
		ret = max(ret, dfs(y + 1, ((n % 2) == 1 ? 1 : 2), amount));

	return ret;
}

bool visited1[MAX * 2]; 
bool visited2[MAX * 2]; 
int bishop[2];

void DFS(int cnt, int x, int y, int color) {
	if (x > n) {
		y++;
		if (x % 2 == 0) x = 1;
		else x = 0;
	}
	if (y > n) {
		if (cnt > bishop[color])
			bishop[color] = cnt;
		return;
	}

	if (pan[y][x] && !visited1[x + y + 1] && !visited2[x - y + n]) {
		visited1[x + y + 1] = true;
		visited2[x - y + n] = true;
		DFS(cnt + 1, x + 2, y, color);
		visited1[x + y + 1] = false;
		visited2[x - y + n] = false;
	}
	DFS(cnt, x + 2, y, color);
}

void init() {
	result = 0;
	bishop[0] = 0; bishop[1] = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			xCntNum[i][j] = i + j - 2;
			yCntNum[i][j] = n - (i - j) - 1;
		}
	}
}

int main() {
	srand(time(NULL));

	//cin >> n;
	while (true) {
		n = 7;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				//cin >> pan[i][j];
				pan[i][j] = rand() % 2;
				cout << pan[i][j] << ' ';
			}
			cout << endl;
		}

		init();

		DFS(0, 1, 1, 0);
		DFS(0, 2, 1, 1);

		result = dfs(1, 1, 0);
		result += dfs(1, 2, 0);


		cout << bishop[0] + bishop[1] << '\n';
		cout << result << '\n';

		if (bishop[0] + bishop[1] != result)
		{
			cout << "답이다름!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!";
		}
	}

	return 0;
}

 

태그 : #1799 비숍 #BOJ 비숍 #백트래킹 #비숍 반례