[DFS, 백트래킹] BOJ 1799 비숍 (C++)

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

1799번: 비숍

 

문제 해결 알고리즘

 

비숍의 특성을 이해해야하는 문제.

 

체스판에 검은색 타일의 비숍과 흰색 타일의 비숍은 서로 공격할 수 없다. 그렇기 때문에 검은색 비숍과 흰색 비숍을 따로 구분해서 깊이 우선 탐색을 진행해야할 필요가 있다.

 

만약에 그냥 색깔 상관없이 모든 타일의 비숍을 한 번에 깊이 우선탐색을 진행한다면 시간초과가 난다.

그렇게 한다면 시간 복잡도는 $O(2^{(N*N)})$ 이지만 위의 방식대로 색깔 구분해서 탐색을 진행해준다면 $O(2^{(N/2 * N/2)})$ 으로 줄일 수 있다.

 

이렇게 색깔로 구분해서 백트래킹을 해주는 아이디어를 떠올리기 좀 힘들었던 문제였던 거 같다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int chessBoard[11][11];
int N;
int black_result = 0, white_result = 0;
//비숍이 들어갈 수 있는 위치 검은 비숍과 흰 비숍으로 구분
vector<pair<int, int>> blackEmptyArea;
vector<pair<int, int>> whiteEmptyArea;
//비숍이 현재 있는 위치 
vector<pair<int, int>> black_bishop;
vector<pair<int, int>> white_bishop;

// 비숍은 2, 비숍이 있을 수 있는 자리는 1, 비숍이 있을 수 없는 자리는 0

bool black_promising(int idx){
    
    int x, y; 

    if(!black_bishop.empty()){
        x = blackEmptyArea[idx].first;
        y = blackEmptyArea[idx].second;
    }
    
    for(int i=0;i<black_bishop.size();i++){

    //다른 비숍의 사정 거리 안에 들어온 경우
    if(x-y == black_bishop[i].first-black_bishop[i].second || x+y == black_bishop[i].first+black_bishop[i].second) return false;

    }
    
    return true;
}


bool white_promising(int idx){

    int x, y;

    if(!white_bishop.empty()){
        x = whiteEmptyArea[idx].first;
        y = whiteEmptyArea[idx].second;
    }

    for(int i=0;i<white_bishop.size();i++){

        //다른 비숍의 사정 거리 안에 들어온 경우
        if(x-y == white_bishop[i].first-white_bishop[i].second || x+y == white_bishop[i].first+white_bishop[i].second) return false;
        
    }

    return true;
}


void black_dfs(int idx){

    if(idx == blackEmptyArea.size()) {

        if(black_result < black_bishop.size()) black_result = black_bishop.size();
        
        return;
    }

    //유망하다면 비숍을 두고 다음꺼 탐색
    if(black_promising(idx)){

        int x = blackEmptyArea[idx].first;
        int y = blackEmptyArea[idx].second;

        

        black_bishop.push_back({x, y});
        chessBoard[x][y] = 2;

        black_dfs(idx+1);

        black_bishop.pop_back();
        chessBoard[x][y] = 1;

    }
    

    black_dfs(idx+1);

}



void white_dfs(int idx){

    if(idx == whiteEmptyArea.size()) {

        if(white_result < white_bishop.size()) white_result = white_bishop.size();
        
        return;

    }

    //유망하다면 비숍을 두고 다음꺼 탐색
    if(white_promising(idx)){

        int x = whiteEmptyArea[idx].first;
        int y = whiteEmptyArea[idx].second;

        

        white_bishop.push_back({x, y});
        chessBoard[x][y] = 2;

        white_dfs(idx+1);

        white_bishop.pop_back();
        chessBoard[x][y] = 1;

    }
    

    white_dfs(idx+1);

}


int main(){
    cin >> N;

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> chessBoard[i][j];

            if(chessBoard[i][j] == 1){
                if((i+j)%2 == 0) blackEmptyArea.push_back({i, j});
                else whiteEmptyArea.push_back({i, j});
            } 
        }
    }

    white_dfs(0);
    black_dfs(0);

    cout << black_result + white_result;

    return 0;
}