[백준 알고리즘] 1799번 비숍 문제풀이 c++

체스판을 검정과 흰색으로 나눠서 계산해야되는 점과

체스판이 홀수일 때, 짝수일 때 구분하는 것을 하지 않아서 한참 헤맸다ㅜㅜ

 

비숍은 체스판에서 흰색 위에 있으면 흰색에서만 움직이고,

검정색 위에 있으면 검정색에서만 움직인다.

따라서 검정색일 때 flag가 false, 흰색일 때는 flag가 true로 구분하여

black_cnt와 white_cnt의 max값을 구하였다.

 

l[20]과 r[20]은 각각 왼쪽 아래 대각선(/),오른쪽 아래 대각선 방향(＼)으로 비숍을 움직일 수 있는지 저장한 배열이다.

왼쪽 아래 대각선상에 놓인 값들은 x+y값이 모두 같으며,

오른쪽 아래 대각선상에 놓인 값들은 x-y값이 모두 같다.

(x-y값은 -n~n의 값을 가지므로 +n을 한다)

 

x,y 위치에 비숍을 놓을때와

(board[x][y]가 1이면서, l[x+y], r[x-y+n]이 false, cnt값 증가)

x,y 위치에 비숍을 안 놓을 때

(cnt값 증가X)

각각 DFS를 호출하여

모든 경우를 탐색한다.

 

DFS호출 시엔 y를 2증가 시켜 

흰색에 위치한 비숍은 흰색만, 검은색에 위치한 비숍은 검은색만 탐색하도록 한다.

y가 n이상이면 x를 1증가하고, 

y가 2의 배수이면 0, 아니면 1로 바꾼다.(줄 바꿈)

 

y가 n이면 각 flag에 맞춰 black_cnt, white_cnt의 최대값을 구한다.

비숍의 최대 개수는 DFS탐색 후 black_cnt에 white_cnt를 더한 값이다.

 

#include <iostream>

using namespace std;

int n, white_cnt, black_cnt;
int board[10][10];
bool l[20],r[20];

void DFS(int x, int y, int cnt, bool flag){
	if(y>= n){
		x++;
		if(y % 2 == 1)
			y = 0;
		else
			y = 1;
	}

	if(x == n){
		if(!flag){
			black_cnt = max(black_cnt, cnt);
		}
		else{
			white_cnt = max(white_cnt, cnt);
		}
		return;
	}
	if(board[x][y] == 1 && !l[x+y] && !r[x-y+n]){
		l[x+y] = true;
		r[x-y+n] = true;
		DFS(x, y+2, cnt+1, flag);
		l[x+y] = false;
		r[x-y+n] = false;
	}
	DFS(x, y+2, cnt, flag);
}
int main(){
	cin >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> board[i][j];
		}
	}

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

	cout << black_cnt + white_cnt;

	return 0;
}