[BOJ 1799] 비숍

이문제를 일반적인 백트래킹 방식으로 풀면 N이 최대 10일때 최대 2^100 경우의수가 생겨 시간초과가 된다.

그래서 발상의 비약이 필요한 문제고 그 아이디어는 체스판을 분할하는것이다.

 

체스판을 보면 흑과 백으로 나뉘어지는데 이것이 비숍의 공격방향과 일치한다.

비숍의 입장에서는 흑과 백은 서로 독립적이라 붙어만 있을뿐이지 서로 영향을 미치지 못한다.

따라서 흑과 백으로 나누면 N이 10일때 N이 5인 체스판 두개로 생각할수 있고 시간복잡도는

2^(25) = 33554432로 충분히 시간안에 해결할수 있는 문제가 된다.

 

비숍의 공격방향은 대각선이라 BFS같이 상하좌우로 움직이는것과는 달리 약간의 수학적 테크닉이 사용된다.

/ 방향 대각선은 x+y로 나타낼수있다. \ 대각선은 x-y+n-1로 나타낼수 있다. 많이 쓰이는 수식이기 때문에

BFS처럼 외워서 익숙해 지도록하자.

 

 

체스판

 

자세한 코드와 주석은 아래와 같다.

 

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

int n;
// 1은 흑 0은 백으로 보드를 나눈다.
// 보드를 45도 왼쪽으로 기운 상태에서 봐야 이해하기가 쉽다.

vector<pair<int,int>> board[2][20];

bool isused[2][20];

int cnt[2];

void func(int idx, int c, int color){
  if(idx == 2*n){
    cnt[color] = max(cnt[color], c);
    return;
  }

  for(auto e:board[color][idx]){ // \ 이 대각선 방향에 있는 좌표들에서
    int x,y;
    tie(x,y) = e;
    if(isused[color][x+y]) continue; // / 이 대각선에 비숍이 있으면 놓을수가 없다.
    isused[color][x+y] = 1;
    func(idx+1, c+1, color);
    isused[color][x+y] = 0;
  }

  func(idx+1, c, color);


}


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++){
      int d;
      cin >> d;
      if(d){

        // 흑과 백으로 구분해서 넣고 \ 이 방향이 같은 좌표는 같은 벡터에 푸쉬 해야함 
        board[(i+j+1) % 2][i-j+n-1].push_back({i,j});
      }
    }
  }

  func(0,0,1);
  func(0,0,0);

  cout << cnt[0] + cnt[1] << '\n';


}