1799번 비숍

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

핵심

1. 검은색과 하얀색은 비숍의 영향을 받지 않으므로, 나누어 계산한다.

2. 비숍을 놓은 경우와 놓지 않는 경우 둘 다 고려해줘야 한다.

3. 오른쪽 대각선은 행 + 열이 일정하고, 왼쪽 대각선은 행 - 열이 일정하다. 

다만, N을 더한 이유는 배열 인덱스가 음수가 나오지 않기 위함이다.

4. 백트래킹 말고, 이분 매칭으로 풀 수 있다. https://www.crocus.co.kr/774

검흰검흰검

흰검흰검흰

검흰검흰검

흰검흰검흰

검흰검흰검

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
#define MAX 40
 
int N = 0;
 
int Map[MAX][MAX] = { 0, };
 
bool diag1[2][MAX*MAX] = { false, };
 
bool diag2[2][MAX*MAX] = { false, };
 
int color = 0;
 
int ans[2] = { 0, };
 
void backtracking(int r, int c, int cnt)
{
    ans[color] = max(ans[color], cnt);
 
    if (c >= N)
    {
        ++r;
 
        if (r % 2 == 0) // 짝수 행이라면
        {
            if (color == 0)    c = 0; // 검은색을 하고 있다면, 열(c)을 0부터 시작.
            else c = 1; // 하얀색을 하고 있다면, 열(c)을 1부터 시작.
        }
        else // 홀수 행이라면
        {
            if (color == 0)    c = 1; // 검은색을 하고 있다면, 열(c)을 1부터 시작.
            else c = 0; // 하얀색을 하고 있다면, 열(c)을 0부터 시작.
        }
    }
 
    if (r >= N) return;
 
    if (Map[r][c] == 1 && !diag1[0][r + c] && !diag2[1][N + r - c])
    {
        diag1[0][r + c] = true;
        diag2[1][N + r - c] = true;
 
        backtracking(r, c + 2, cnt + 1); // 비숍을 놓는 케이스
 
        diag1[0][r + c] = false;
        diag2[1][N + r - c] = false;
    }
    
    backtracking(r, c + 2, cnt); // 비숍을 놓지 않는 케이스
}
 
int main(void)
{
    int result = 0;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &Map[i][j]);
        }
    }
 
    color = 0; // black
 
    backtracking(0, 0, 0);
 
    color = 1; // white
 
    backtracking(0, 1, 0);
 
    result = ans[0] + ans[1];
 
    printf("%d\n", result);
    
    return 0;
}