백준 1799번 : 비숍 (C++)

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

1799번: 비숍

 

 

 

 

 

 

체스판에 비숍을 최대 몇개까지 놓을 수 있는지 찾는 문제. 일단 뻔하지만 백트래킹 문제다. 그래서 처음에 별 생각없이 모든 경우에 대해 백트래킹을 시도해니 시간초과 해버렸다... 고민좀 하다가 인터넷에서 풀이를 참고하였다.

 

생각해보면 체스판은 흑, 백으로 나누어져 있다. 그리고 체스좀 둬본 사람은 알겠지만 비숍은 대각선으로만 이동이 가능하니 다른 색깔의 위치로는 이동이 불가하다. 즉 흑에 있는 비숍은 백의 칸에 대해 영향령이 미치지 못하고 그 반대도  마찬가지다. 그래서 흑과 백의 경우를 각각 따로 백트래킹 해주면 시간복잡도가 O(2^NxN) 에서 O(2^(N/2)x(N/2))로 확줄어들게 된다. 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include<cstring>
#include <cmath>
#include <set>
#include <queue>
#include <unordered_map>
#include <deque>
#include <string>

typedef long long ll;

using namespace std;



using namespace std;
int n;
int map[101][101];
int colo[101][101];
int ans[2];
int leftd[101]; //왼->오 방향 대각선
int rightd[101]; // 오->왼 방향 대각선


void dfs(int now, int depth, int color){
	
	for(int i=now; i<=n*n; i++){
		int row = (i%n == 0)? i/n : i/n + 1;
		int col = (i%n == 0)? n : i%n;
		if(colo[row][col] != color) continue;
		if(map[row][col] == 1 && leftd[col-row +n]==0 && rightd[col+row-1] ==0){
			leftd[col-row +n] = 1;
			rightd[col+row-1] =1;
			dfs(i+1, depth+1, color);
			leftd[col-row +n] = 0;
			rightd[col+row-1] =0;
		}
	}

	if(ans[color] < depth){
		ans[color] = depth;
	}
	
}

int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> n;
   
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++){
			cin >> map[i][j];	
			if(i%2 ==0 && j%2 ==0){
				colo[i][j] = 1;
			}
			if(i%2 == 1 && j%2 ==1){
				colo[i][j] = 1;
			}
		}
	
	dfs(1,0,1);
	dfs(1,0,0);
   
	cout << ans[0] + ans[1];
}