BOJ 1799 비숍

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

1799번: 비숍

 

백트래킹을 사용해 풀 수 있는 문제입니다. n-queen 문제와 비슷하게 비숍을 하나씩 놓는다고 생각하고, 하나의 비숍이 놓일 때 그 대각선에 있는 칸들은 전부 갈 수 없다고 표시해주면 됩니다. 다만 나이브하게 백트래킹을 돌리면 시간초과를 받게 되고, 체스칸의 흰색 영역과 검정색 영역을 나눠서 (비숍은 한 색으로만 이동할 수 있으므로) 풀면 풀 수 있습니다. 이 아이디어를 생각하는 것이 어려웠습니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

//2d graph search////////////////////////////////////////////////////////////////////

bool inrange(int i, int j, int n, int m) { return 0 <= i && i < n && 0 <= j && j < m; }

/////////////////////////////////////////////////////////////////////////////////////

using namespace std;

int T, n, graph[15][15];
int cnt, ans;
vector<int> vec;

int bw(int x, int y) {
  return ((x % 2) + (y % 2)) % 2;
}

void check(int pos, int op) {
  int x = pos / n;
  int y = pos % n;

  for (int i = 1; i <= 10; i++) {
    if (inrange(x + i, y + i, n, n)) graph[x + i][y + i] += op;
    if (inrange(x + i, y - i, n, n)) graph[x + i][y - i] += op;
    if (inrange(x - i, y + i, n, n)) graph[x - i][y + i] += op;
    if (inrange(x - i, y - i, n, n)) graph[x - i][y - i] += op;
  }
}

void find(int pos) {
  cnt++;
  ans = max(ans, cnt);
  check(pos, 1);

  for (int i = pos + 1; i < n * n; i++) {
    int x = i / n;
    int y = i % n;
    if (bw(pos / n, pos % n) != bw(x, y)) continue;
    if (graph[x][y]) continue;
    find(i);
  }

  cnt--;
  check(pos, -1);
}

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        int x;
        cin >> x;
        if (!x) graph[i][j]++;
      }
    }

    int ans1 = 0;
    int ans2 = 0;

    for (int i = 0; i < n * n; i++) {
      if (bw(i / n, i % n)) continue;
      if (graph[i / n][i % n]) continue;
      find(i);
      ans1 = max(ans, ans1);
      ans = 0;
      cnt = 0;
    }

    for (int i = 0; i < n * n; i++) {
      if (!bw(i / n, i % n)) continue;
      if (graph[i / n][i % n]) continue;
      find(i);
      ans2 = max(ans, ans2);
      ans = 0;
      cnt = 0;
    }

    cout << ans1 + ans2 << endl;
  }

  return 0;
}