백준 - 1799 비숍

문제

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

1799번: 비숍

체스판에 놓을 수 있는 비숍의 최대 개수를 구하는 문제였다.

 

문제 풀이

시간 제한이 10초나 되는 문제였지만 완탐으로 하니 시간 초과가 나왔다. 어떻게 줄여야 할지 감도 잡히지 않아 검색해 보니 비숍은 2가지 경우에는 절대 서로를 잡을 수 없다고 했다. 아래와 같이 o인 칸과 x인 칸은 아예 다른 경우로 생각하면 된다. 원래는 전체 칸을 다 살펴야 했지만 나눠 생각하면 o인 칸, x인 칸을 따로 생각할 수 있고 이를 통해 시간을 줄일 수 있었다.

o x o x o
x o x o x
o x o x o
x o x o x

 

먼저 위와 같이 전체 Arr을 두 가지로 나눈 numArr을 초기화 해줬다.

 

dfs를 돌릴 때, 비숍을 놓지 않는 경우와 놓는 경우 2가지로 나눠 백트래킹을 진행했다. 놓는 경우에는 해당 자리가 현재 num 값과 같은지와 대각선 방향에 비숍이 있는지 확인해서 놓을 수 있다면 놓게 했다.

/*
2가지 경우로 나눠서 dfs
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0

*/

int N;
vector<vector<int>> arr;
vector<pair<int, int>> canBishop;
vector<vector<int>> numArr;
int dx[4] = { -1,-1,1,1 };
int dy[4] = { 1,-1,1,-1 };
int maxCnt = 0;

void printMap() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printf("%d ", arr[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

void initNumArr() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i % 2 == 0) {
				if (j % 2 == 0) {
					numArr[i][j] = 0;
				}
				else numArr[i][j] = 1;
			}
			else {
				if (j % 2 == 0) {
					numArr[i][j] = 1;
				}
				else numArr[i][j] = 0;
			}
		}
	}
}

//비숍 놓은 곳 : 5
//0이었던 곳 바꿀 때 : 0 -> 2
//1이었던 곳 바꿀 때 : 1 -> 3
void changeMap(int ox, int oy, pair<int, int> n) {
	int zero = n.first;
	int one = n.second;

	//비숍 놓기
	if (one == 3) arr[ox][oy] = 5;
	else arr[ox][oy] = one;

	for (int i = 0; i < 4; i++) {
		int x = ox;
		int y = oy;

		while (true) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
				//0 -> 2  혹은 2 -> 0
				if (arr[nx][ny] == zero + 2 || arr[nx][ny] == zero - 2) {
					arr[nx][ny] = zero;
				}
				else {
					arr[nx][ny] = one;
				}
			}
			else break;

			x = nx;
			y = ny;
		}
	}
}

bool canSet(int ox, int oy) {
	bool flag = true;
	if (arr[ox][oy] != 1 && arr[ox][oy] != 3) return false;

	for (int i = 0; i < 4; i++) {
		int x = ox;
		int y = oy;

		while (true) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
				//1인 부분에 비숍이 있어야 잡을 수 있음
				if (arr[nx][ny] == 5) {
					flag = false;
					break;
				}
			}
			else break;

			x = nx;
			y = ny;
		}
		if (!flag)break;
	}
	return flag;
}

void dfs(int index, int cnt, int num) { //num 0: 0인 곳만 가능, num 1: 1인 곳만 가능
	
	if (index == canBishop.size()) {
		//printf("cnt: %d\n", cnt);
		//printMap();
		maxCnt = max(cnt, maxCnt);
		return;
	}

	//최대값보다 작은 경우
	if (cnt + (canBishop.size() - index - 1) < maxCnt) return;

	int x = canBishop[index].first;
	int y = canBishop[index].second;

	

	//index 위치에 안 놓는 경우
	dfs(index + 1, cnt,num);


	//index 위치에 놓을 경우	
	//num이 아님, 못 놓는 경우
	if (numArr[x][y] == num) {
		if (canSet(x, y)) {
			//printf("set!\n");
			//arr 변경
			changeMap(x, y, { 2,3 });
			dfs(index + 1, cnt + 1, num);
			//arr 원복
			changeMap(x, y, { 0,1 });
		}
	}



}

int main() {

	scanf("%d", &N);

	arr = vector<vector<int>>(N, vector<int>(N));
	numArr = vector<vector<int>>(N, vector<int>(N));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &arr[i][j]);
			if (arr[i][j] == 1) {
				canBishop.push_back({ i,j });
			}
		}
	}

	initNumArr();

	dfs(0, 0,0);
	int answer = maxCnt;
	maxCnt = 0;
	dfs(0, 0,1);
	answer += maxCnt;
	printf("%d", answer);

	return 0;
}

/*
*/