문제

1799번: 비숍

풀이

문제를 보자마자 처음 든 생각은 "그리디로 풀 수 있지 않을까?" 였습니다. 색칠되지 않은 위치에 비숍을 놓았을 때 놓을 수 없어지는 비숍의 수를 우선순위로 하여 적은 것부터 놓게 된다면 문제를 해결할 수 있다고 생각했습니다. 하지만 모든 비숍의 우선순위 조건이 같은 경우 문제가 발생했습니다. 같을 경우 다음 우선순위를 무엇으로 잡아야하는지 알 수 없었기 때문에 그리디로 해결할 수 없었습니다.

따라서 백트래킹으로 모든 경우의 수를 확인해야 합니다.
체스판 임의의 칸에 비숍을 두는 경우, 두지 않은 경우를 고려하여 마지막 칸 차례까지 확인 후 가장 비숍을 많이 둔 경우를 채택합니다.

하지만 n*n 크기의 체스판을 하나씩 돌며 확인하면 $2^{100}$으로 엄청난 시간이 걸리게 됩니다.

체스판에서 흰색 칸에 있는 비숍은 어떻게 움직여도 절대 검은색 칸으로 이동할 수 없습니다. 비숍의 위치는 같은 색상 칸에만 영향을 받기 때문에 흰색칸과 검은색칸을 독립적으로 탐색하여 시간비용을 줄일 수 있습니다.

어떤 위치에 비숍을 두어도 되는지 확인하는 방법은 대각선 방향 위치 인덱스의 x+y, x-y값을 이용합니다.
어떤 위치의 오른쪽 위, 왼쪽 아래 방향으로는 x+y의 값이 동일합니다.
어떤 위치의 왼쪽 위, 오른쪽 아래 방향으로는 x-y의 값이 동일합니다.

체스판의 대각선방향으로 비숍이 있는지 없는지 확인하기 위해 x+y, x-y의 값이을 인덱스로 하는 배열의 true인지 false인지를 확인하여 판단할 수 있습니다.
n*n 크기라면 필요한 개수는 n*2개가 필요합니다. 오른쪽 위 방향, 오른쪽 아래 방향 두가지를 준비하여 각각 x+y, x-y+(n-1)로 인덱스를 설정합니다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<vector<bool>> board;
vector<bool> incr;
vector<bool> decr;
int odd = 0;
int even = 0;
// int answer[2] = {0, 0};

int max(int a, int b) { return a > b ? a : b; }

void dfs(int x, int y, int cnt, bool isOdd)
{
    if (y >= n)
    {
        x += 1;
        if(y % 2 == 0) y = 1;
        else y = 0;
    }
    if (x >= n)
    {
        // answer[isOdd] = max(answer[isOdd], cnt);
        int& answer = isOdd ? odd : even;
        answer = max(answer, cnt);
        return;
    }

    if (board[x][y] && !incr[x + y] && !decr[x - y + n-1])
    {
        incr[x+y] = true;
        decr[x-y+n-1] = true;
        dfs(x, y+2, cnt+1, isOdd);
        incr[x+y] = false;
        decr[x-y+n-1] = false;
    }

    dfs(x, y+2, cnt, isOdd);
}

int main()
{
    cin >> n;
    board = vector(n, vector<bool>(n, false));
    incr = vector<bool>(n*2, false);
    decr = vector<bool>(n*2, false);
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; ++j)
        {
            bool temp;
            cin >> temp;
            board[i][j] = temp;
        }
    }

    dfs(0, 0, 0, false);
    dfs(0, 1, 0, true);
    
    cout << odd + even << endl;
    return 0;
}