[백트랙킹]백준1799번 비숍

백준1799 비숍

N-Queens 문제와 비슷하게 백트랙킹으로 해결할 수 있는 문제였다.

전체 체스판은 오른쪽 대각선과 왼쪽 대각선으로 나눌 수 있다.

비숍은 대각선으로만 움직일 수 있기 때문에 하나의 비숍을 놓았을 때 해당 비숍이 움직일 수 있는 대각선들을 사용하지 못하게 만든다.

최대로 놓는 경우이기 때문에 해당 대각선들을 가능한 많이 막아주면 된다.

체스판과 대각선에 대한 자세한 내용은 N-Queens를 참고하면 된다.

체스판에는 다음과 같은 오른쪽 대각선이 존재한다.

하나의 비숍이 정해지면 같은 오른쪽 대각선에 존재하는 칸들에는 다른 비숍이 들어올 수 없다.

두 개의 칸이 같은 오른쪽 대각선에 존재하는 지의 여부는 x+y의 값이 같은지의 여부로 알 수 있다.

예를 들어 (1,2)와 (3,0) 은 x+y의 값이 같기 때문에 같은 오른쪽 대각선 상에 있다.

체스판에는 다음과 같은 왼쪽 대각선이 존재한다.

하나의 비숍이 정해지면 같은 왼쪽 대각선에 있는 칸들에는 다른 비숍이 들어올 수 없다.

두 개의 칸이 같은 왼쪽 대각선에 속하는 지의 여부는 x-y의 값이 같은 지의 여부로 알 수 있다.

다만 빼기 연산은 값이 마이너스까지 나온다. 위의 4 * 4 체스판을 예로 들면, 아래서부터

-3, -2, -1, 0, 1, 2, 3 이 나오기 때문에 N -1 을 더해줘서 0부터 시작하게 만들어줘야 한다.

그 다음은 백트랙킹의 영역이다.

입력을 받을 때 들어오는 1들을 따로 벡터에 담고, 그 안에서 백트랙킹을 수행하면 된다.

만약 해당 1 칸에 아직 비숍이 놓아지지 않았고 같은 오른쪽, 왼쪽 대각선 상에 모두 비숍이 없다면 비숍을 놓게 만들어준다.

void btk_0(int n){
    if(n==v_0.size()){
        if(bishopCount_0 > answer_0) answer_0 = bishopCount_0;
        return;
    }
    for(int i=n;i<v_0.size();i++){
        if(!isUsed_0[i] && !upRight[v_0[i].first+v_0[i].second] && !upLeft[v_0[i].second - v_0[i].first + N - 1] ){
            isUsed_0[i] = true;
            upRight[v_0[i].first+v_0[i].second] = true;
            upLeft[v_0[i].second - v_0[i].first + N - 1] = true;
            bishopCount_0++;
            btk_0(i+1);
            bishopCount_0--;
            isUsed_0[i] = false;
            upRight[v_0[i].first+v_0[i].second] = false;
            upLeft[v_0[i].second - v_0[i].first + N - 1] = false;
        }
    }
    
}

다만 의아한 것은 종료조건일텐데, 백트랙킹의 종료 조건은 모든 1을 검사한 경우이다.

따라서 백트랙킹 함수로는 현재 내가 검사한 1이 몇 번째 1이었는지를 넘겨주게 되면 된다.

여기까지 수행했다면 정답이긴 하지만 시간초과가 발생한다.

10초라서 매우 넉넉하다고 생각했는데 아니었다.

여기저기 찾아본 결과 시간 초과가 발생하지 않게 하려면 처음부터 입력으로 들어오는 1들을 두 가지 종류로 나눠야 한다.

체스판 위에서 하얀색 칸 위에 있는 비숍은 하얀색 칸으로만 갈 수 있고, 검정색 칸 위에 있는 비숍은 검정색 칸 위로만 갈 수 있다.

검정색 칸인지 하얀색 칸인지는 해당 칸의 x, y 좌표를 더한 값을 2로 나눈 나머지를 이용하면 된다.

따라서 1을 두 개로 분류한 뒤 각각의 그룹에 대해 백트랙킹을 수행하고 마지막에 결과를 더해주면 된다.

이 과정을 생략할 경우 시간 초과가 나는 이유는 하얀색 비숍인 경우에는 검정색 비숍을 무시해도 되는데도 불구하고 모두 확인하기 때문이다.

#include <iostream>
#include <vector>

using namespace std;
bool upRight[25];
bool upLeft[25];

int N;
int answer = 0;
int answer_0 = 0;
int answer_1 = 0;
int bishopCount = 0;
int bishopCount_0 = 0;
int bishopCount_1 = 0;
int board[11][11];
vector<pair<int,int> > v;
vector<pair<int,int> > v_0;
vector<pair<int,int> > v_1;
vector<bool> isUsed;
vector<bool> isUsed_0;
vector<bool> isUsed_1;

void btk_0(int n){
    if(n==v_0.size()){
        if(bishopCount_0 > answer_0) answer_0 = bishopCount_0;
        return;
    }
    for(int i=n;i<v_0.size();i++){
        if(!isUsed_0[i] && !upRight[v_0[i].first+v_0[i].second] && !upLeft[v_0[i].second - v_0[i].first + N - 1] ){
            isUsed_0[i] = true;
            upRight[v_0[i].first+v_0[i].second] = true;
            upLeft[v_0[i].second - v_0[i].first + N - 1] = true;
            bishopCount_0++;
            btk_0(i+1);
            bishopCount_0--;
            isUsed_0[i] = false;
            upRight[v_0[i].first+v_0[i].second] = false;
            upLeft[v_0[i].second - v_0[i].first + N - 1] = false;
        }
    }
    
}
void btk_1(int n){
    if(n==v_1.size()){
        if(bishopCount_1 > answer_1) answer_1 = bishopCount_1;
        return;
    }
    for(int i=n;i<v_1.size();i++){
        if(!isUsed_1[i] && !upRight[v_1[i].first+v_1[i].second] && !upLeft[v_1[i].second - v_1[i].first + N - 1] ){
            isUsed_1[i] = true;
            upRight[v_1[i].first+v_1[i].second] = true;
            upLeft[v_1[i].second - v_1[i].first + N - 1] = true;
            bishopCount_1++;
            btk_1(i+1);
            bishopCount_1--;
            isUsed_1[i] = false;
            upRight[v_1[i].first+v_1[i].second] = false;
            upLeft[v_1[i].second - v_1[i].first + N - 1] = false;
        }
    }
    
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> board[i][j];
            
            if(board[i][j]==1){
                if((i+j)%2 == 0){
                    v_0.push_back(make_pair(i, j));
                    isUsed_0.push_back(false);
                }
                else{
                    v_1.push_back(make_pair(i, j));
                    isUsed_1.push_back(false);
                }
//                v.push_back(make_pair(i, j));
//                isUsed.push_back(false);
            }
        }
    }
//    btk(0,(v[0].first+v[0].second));
    btk_0(0);
    btk_1(0);
    cout << answer_0 + answer_1;
}