[백준 1799번] 비숍 (C++)

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

 

N-Queen하고 사실상 똑같은 문제라고 생각한다.

N-Queen에서는 퀸이 한 열에 한개밖에 못놓는 것을 기준으로 재귀를 돌렸다.

비숍은 한 열에는 여러개가 올 수 있고 각 대각선에 한개씩 밖에 못오기 때문에 대각선을 기준으로 재귀를 돌리면 된다.

 

우상향 대각선을 기준으로 재귀를 돌렸고 어느 대각선을 기준으로 잡는지는 당연히 상관이 없다.

그림으로 보면 다음과 같이 탐색했다.

특정 칸에 도착했을 때 그 칸이 비숍이 놓을 수 있는 자리이고 화살표 방향과 수직인 대각선상에 다른 비숍이 없다면 비숍을 놓으면서 탐색해나가면 된다.

 

대각선을 구분하는 방법은 N-Queen포스팅 때 했지만 저 2n-1개의 대각선을 각각 인덱싱한다.

대각선으로 해당하는 모든 칸을 인덱싱 할 수 있는 이유는 "row+col=일정" 하기 때문이다.

수직인 대각선도 당연히 인덱싱을 해야 검사가 가능한데 화살표와 수직인 대각선은 "row-col=일정" 하기 때문에 음수를 방지에서 적당한 값을 더해서 진행한다.

 

추가로 비숍은 대각선 방향으로만 진행하기 때문에 분할정복을 적용하여 시간복잡도를 크게 줄일 수 있다.(흑색,백색 따로)

분할정복 없이 재귀를 돌리면 2^(n^2) 의 시간복잡도가 나오지만 둘로 나눈 것을 두번 계산함으로써 2^(2n)의 시간복잡도로 해결할 수 있다.

 

구현은 N-Queen에서 소개한 마지막 방법인 비트마스킹을 이용했다

#include <iostream>
using namespace std;

int n, board[10][10], diag1[21], diag2[21], total;

int trial(int diag, int mem, int cnt, int kind){
  if(diag == 2*n-1) return cnt;

  int ret = cnt;
  int x = (diag < n) ? diag : n-1;
  int y = (diag < n) ? 0 : diag-n+1;

  while(x >= 0 && y < n){
    if((x+y)%2==kind && board[x][y]){
      //검사할 우하향 대각선 인덱스
      int idx = x-y+n-1;
      if(!(mem & (1<<idx))) ret = max(ret,trial(diag+1,mem|(1<<idx), cnt+1, kind));
    }
    x--,y++;
  }
  return max(ret,trial(diag+1,mem,cnt,kind));
}

int main(){
  cin >> n;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cin >> board[i][j];
    }
  }

  total = trial(0,0,0,0);
  total += trial(0,0,0,1);
  cout << total;

}