[백준 1799] 비숍 C++

1799번: 비숍

백트래킹 연습하기 #4

---

1. 문제풀이 아이디어

비숍의 특징 : 체스판의 검은 칸에 있는 비숍과 흰색 칸에 있는 비숍은 서로 아무 영향을 끼칠 수 없다.

이 문제를 정석적인 백트래킹으로 푼다면 시간 복잡도는 O(2^(N*N))이 된다..

체스판에 모든 곳에 비숍을 놓을 수 있고 N=10이면 각각의 칸마다 ( 비숍을 놓는다 or 놓지않는다 ) 2가지의 경우가 생기므로 2^100가지의 경우를 모두 탐색해야한다 

2^100 = 1.2676506e+30 이므로 참신한 방법이 필요하다

 

1차 코드를 작성하고 비숍의 특징을 떠올리지 못해서 O(2^100)짜리 코드를 어떻게 수정할지 막막한 상태였다.

도저히 생각이 안나 구글에서 비숍의 특징이라는 아이디어를 얻게 되었다

 

비숍의 특징 덕분에 흰색칸에만 비숍을 놓는 경우와 검은칸에만 비숍을 놓는 경우를 따로 계산할 수 있게 된다.

각각의 경우에 n을 2로 나눌 수 있게되고 시간복잡도는 O(2^(N/2 * N/2))가 된다!!

n이 10일 때 두 경우를 각각 구한다고 해도 O(2 * 2^25)가 되고 이는 약 6천만 정도되는 숫자이기때문에 1초내로 탐색이 가능해진다!

---

2. 코드 설명

비숍은 대각선으로 움직이므로 현재 비숍이 놓일 위치의 대각선 방향에 다른 비숍이 이미 있는지 알고 있어야 한다

N x N Board에서 대각선의 수는 2*N -1 이므로 20칸짜리 boolean 형 배열을 2개 만들어 준다 (각각 기울기 1, -1)

 

int diagl(int r, int c) : r,c 좌표가 -1기울기를 가진 대각선 중 몇 번째인지 반환하는 함수

int diagr(int r, int c) : r,c 좌표가 1기울기를 가진 대각선 중 몇 번째인지 반환하는 함수

 

<+34> ~ <+37> : 현재 위치가 비숍을 놓을 수 없는 위치이거나, Bishop함수 인자의 color와 다르다면 다음 칸으로 넘어간다

<+51> ~ <+55> : 현재 위치의 대각선배열 인덱스에 비숍을 놓고, cnt를 하나 증가시키고 다음 칸으로 넘어간다. 백트래킹을 적용해 되돌아 온다면 대각선배열 인덱스에 비숍을 제거하고 비숍을 놓지 않고 다음 칸으로 넘어간다

#include <bits/stdc++.h>
 
using namespace std;
 
struct P{
    int is_blocked, color; 
};
 
int N, bret = 0, wret = 0;
P Board[11][11];
bool Ldiag_bs[21], Rdiag_bs[21];
 
inline int diagl(int r, int c){
    int ret = r + (N-1-c);
    return ret;
}
inline int diagr(int r, int c){
    int ret = r + c;
    return ret;
}
 
void Bishop(int r, int c, int cnt, int color){
    if(c == N){
        Bishop(r+1, 0, cnt, color);
        return;
    }
    
    if(r == N){
        if(color == 1) bret = max(bret, cnt);
        else if(color == 2) wret = max(wret, cnt);
        return;
    }
    
    if(!Board[r][c].is_blocked || Board[r][c].color != color){
        Bishop(r, c+1, cnt, color);
        return;
    }
    
    int lidx = diagl(r, c);
    int ridx = diagr(r, c);
    
    if(Ldiag_bs[lidx]){
        Bishop(r, c+1, cnt, color);
        return;
    }
    if(Rdiag_bs[ridx]){
        Bishop(r, c+1, cnt, color);
        return;
    }
    
    Ldiag_bs[lidx] = true;
    Rdiag_bs[ridx] = true;
    Bishop(r, c+1, cnt+1, color);
    Ldiag_bs[lidx] = false;
    Rdiag_bs[ridx] = false;
    Bishop(r, c+1, cnt, color);
}
 
void input(){
    int b, c;
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> Board[i][j].is_blocked;
            if((i + j) % 2) Board[i][j].color = 1;
            else Board[i][j].color = 2;
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    input();
    Bishop(0, 0, 0, 1);
    Bishop(0, 0, 0, 2);
    
    cout << bret + wret;
    return 0;
}