백준(BOJ) 1799 : 비숍

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

1799번: 비숍

 

N의 제한이 10이다.

바로 백트래킹이 아닐까? 라는 추측을 할 수 있다.

 

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

9663번: N-Queen

또한 이 문제와 비슷한 문제라는 것 까지 알 수 있을 것이다.

대각선에 비숍이 놓여있는지 확인하는 bool 변수를 만들기 위해 예를들어 5 x 5 보드판이 있을 때의 i + j 좌표값을

넣어보았다. 여기서 우리는 하나의 규칙을 찾을 수 있다.

 

바로 우측에서 좌측으로 내려오는 대각선의 좌표의 합이 모두 같다는 것!

따라서 위와 같은 방향은 x + y 번 인덱스를 확인해줌으로써 비숍이 놓여있는지 확인할 수 있을 것이다.

그렇다면 반대방향은 어떠할까??

 

잘 생각해보면 좌측에서 우측으로 가는 대각선의 경우 x와 y값이 모두 1씩 증가한다는 것을 알 수 있다.

따라서 같은 대각선의 경우에는 y - x 값이 일정하다.

하지만 위에서 구한 방향의 값과 겹칠 수 있기 때문에 ↙방향에서 나오는 인덱스 값과 겹치지 않도록 특정한 수를 더해준다. 내 경우에는 무난하게 큰 값인 50을 더해주었다.

 

이제 우리가 해야할 것은 무엇일까?

바로 그 칸에 비숍을 놓을 수 있을 때 비숍을 놓을 지 말지를 결정하는 것이다.

하지만 보드의 최대 칸 수는 100 (10 x 10)개이므로 이렇게 할 경우 2^100 의 시간복잡도가 계산되므로 시간초과가 발생하게 된다. 그렇다면 이것을 어떻게 해야할까?

 

체스판을 생각해 보았을 때 흰색 칸에 있는 비숍은 흰색 칸에 있는 비숍만 잡을 수 있으며 반대의 경우도 마찬가지이다.

이를 이용해 재귀함수를 두개로 나누자. 흰색 칸을 확인하고 검은색 칸을 확인한다면 해결할 수 있다.

 

이제 X값을 증가시켜주다가 X값이 보드에서 벗어낫을 경우를 생각해보자.

만약 X가 홀수라면 X는 늘 2씩 증가하므로 X가 1인 좌표에서 출발했다는 것을 알 수 있다.

따라서 그 다음 대각선의 X좌표는 2이므로 2로 설정하고 Y를 1증가시켜준다.

반대의 경우는 반대로 생각하면 될 것이다.

 

흰색칸에 있는 비숍의 경우의 최댓값과 검은색칸에 있는 비숍의 경우의 최댓값을 두번의 재귀함수를 통해 더해주어

해결할 수 있었다!

 

아래는 소스코드이다.

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 987654321;

int N;
int board[11][11] = {};
bool flag[50] = {};
bool flag2[101] = {};
int ans = 0;
int cnt = 0;
int ans2 = 0;
int cnt2 = 0;

void solve(int y, int x) {
  if(x >= N + 1) {
    y++;
    if(x % 2 == 0) {
      x = 1;
    }
    else {
      x = 2;
    }
  }
  if(y > N) {
    ans = max(ans, cnt);
    return;
  }
  if(board[y][x] == 1 && flag[y + x] == false && flag2[50 + y - x] == false) {
    flag[y + x] = true;
    flag2[50 + y - x] = true;
    cnt++;
    solve(y, x + 2); // choose
    cnt--;
    flag[y + x] = false;
    flag2[50 + y - x] = false;
  }
  solve(y, x + 2); // dont
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin >> N;

  for(int i = 1 ; i <= N ; i++) {
    for(int j = 1 ; j <= N ; j++) {
      cin >> board[i][j];
    }
  }
  solve(1, 1);
  ans2 += ans;
  ans = 0;
  solve(1, 2);
  ans2 += ans;
  cout << ans2 << endl;
}