백준 1799번 비숍[C++]

1. 문제 풀이

 백트래킹의 well-known 문제인 N-Queen의 응용 set임. Queen 대신 비숍으로 대체 임의의 위치 (x, y)에 비숍이 위치할 때 어떤 대각선과 역대각선을 점유하는지 알아야 함, ( x, y ) 값을 가공해 대각선 정보들을 linear 하게 관리할 수 있음. 체스판의 크기가 N이고 임의의 위치 ( x, y )를 x + y, y - x로 대각선 정보와 역대각선정보를 linear 하게 관리할 수 있음

 

대각선 ( x + y ) = { 0, 1, 2, ..., 2*N-2 }

역대각선 ( y - x ) = { -N + 1, -N + 2,..., 1, 0, 1,..., N-2, N-1 }

 

역대각선은 음수가 나오므로 +N-1를 통해 조정할 필요가 있음

 

역대각선( y - x + N - 1 ) : { 0, 1, 2,..., 2*N - 2 }

 

따라서 체스판의 크기가 N이면 대각선은 각각 2N-1개임을 알 수 있음.

 

이를 바탕으로 비숍을 놓을 수 있는 위치정보를 바탕으로 백트래킹 시도 -> TLE

 

< 개선 >

체스판은 흰색과 검은색판이 교차되어있음, 흰색칸에 위치한 비숍은 검은 칸에 영향을 주지 않음을 알 수 있음. 즉 백트래킹을 흰색판위치와 흑색판 위치를 분리하여 진행  -> AC

 

2. 코드 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n;
bool diag1[20], diag2[20];
vpi white, black;
int white_ans, black_ans;

void select(int k, int depth, int mode){
  (mode ? white_ans : black_ans) = max((mode ? white_ans : black_ans), depth);

  if(k == sz((mode ? white : black)) || depth == sz((mode ? white : black))) return;
  
  for(int i = k; i < sz((mode ? white : black)); i++){
    auto &[x, y] = (mode ? white : black)[i];
    if(!diag1[x+y] && !diag2[y - x + n - 1]){
      diag1[x + y] = 1;
      diag2[y - x + n - 1] = 1;
      select(i+1, depth+1, mode);
      diag1[x + y] = 0;
      diag2[y - x + n - 1] = 0;
    }
  }
}

int main() {
  fastio(nullptr, false);
  
  // input
  cin >> n;
  for(int i = 0; i < n; i++){
    int available;
    for(int j = 0; j < n; j++){
      cin >> available;
      if(!available) continue;
      ((i+j)&1) ? white.pb({i, j}) : black.pb({i, j});
    }
  }

  // solve
  select(0, 0, 0);
  select(0, 0, 1);

  // output
  cout << white_ans + black_ans;
}

 

3. 제출 결과