백준/1799번/비숍/골드1

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

문제 설명

Site: Baekjoon
Number: 1799
Category: Back Tracking
Rank: Gold 1

주어진 체스판에서 비숍을 놓을 수 있는 최댓값을 구하는 문제입니다.

문제 풀이

놓을 수 있는 퀸의 최댓값을 구하는 9663번 N-Queen문제와 흡사하지만 대각선만 판별하는 문제입니다.

9663번 문제는 한 행 또는 열에 하나의 퀸 밖에 두지 못했기 때문에 각 행마다 놓을 수 있는 위치를 판별 후 놓을 수 있었던 최댓값을 도출해내는 방법을 사용하였습니다.

이 방법을 대각선으로 바꾸어 왼쪽 아래에서 오른쪽 위로 올라가는 대각선 (2 * N) - 1개와 왼쪽 위에서 오른쪽 아래로 내려가는 대각선 (2 * N) - 1개를 사용하여 판별하였습니다.

최대 10 x 10 공간에서 나올 수 있는 대각선의 갯수는 19개

DownDiagonal: 왼쪽 아래에서 오른쪽 위로 올라가는 대각선. 대각선에 있는 모든 점의 i + j의 값이 같으므로 i + j를 통해 해당 대각선에 비숍이 있는지 판별합니다.
UpDiagonal: 왼쪽 위에서 오른쪽 아래로 내려가는 대각선. 대각선에 있는 모든 점의 i - j의 값이 같지만 음수가 나오므로 + N - 1을 통해 최소 0 ~ 최대 18의 대각선 번호를 매겨 대각선에 비숍이 있는지 판별합니다.

모든 배열을 돌며 진행하여도 되지만, 실제 체스판을 고려해본다면 검은색 위의 비숍은 검은색으로만 이동이 가능하고 흰색 위의 비숍은 흰색만 이동이 가능하기 때문에 이를 나누어 계산하면 시간복잡도가 반으로 줄어듭니다.

추가로, 배열을 돌며 진행하면 지속적으로 해당 체스판이 0인지 1인지 고려해야 하기 때문에 검은색 비숍과 흰색 비숍을 따로 배열에 넣어 백트래킹을 진행하였습니다.

백트래킹 과정은 다음과 같습니다.

Black 또는 White 배열의 인덱스에 비숍을 놓을 수 있다면 비숍을 놓은 후에 Find함수를 진행하고 이 후 놓을 수 없거나 놓지 않고 진행하는 경우를 판별하기 위해 놓지 않고 Find를 진행합니다.

모든 배열을 돈 후 ansBlack 또는 ansWhite값의 최댓값을 갱신합니다.

ansBlack + ansWhite값이 비숍을 넣을 수 있는 최댓값으로 도출됩니다.

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

int chess[11][11];

bool DownDiagonal[19];
bool UpDiagonal[19];

int ansBlack, ansWhite, N, B, W;

void FindBlack(vector<PII>& Black, int cnt, int idx)
{
    if (idx == B)
    {
        ansBlack = max(cnt, ansBlack);
        return;
    }

	PII black = Black[idx];

	if (!DownDiagonal[black.first + black.second] && !UpDiagonal[black.first - black.second + N - 1])
	{
		DownDiagonal[black.first + black.second] = true;
		UpDiagonal[black.first - black.second + N - 1] = true;
		FindBlack(Black, cnt + 1, idx + 1);
		UpDiagonal[black.first - black.second + N - 1] = false;
		DownDiagonal[black.first + black.second] = false;
	}

    FindBlack(Black, cnt, idx + 1);
}

void FindWhite(vector<PII>& White, int cnt, int idx)
{
    if(idx == W)
    {
        ansWhite = max(cnt, ansWhite);
        return;
    }

	PII white = White[idx];

	if (!DownDiagonal[white.first + white.second] && !UpDiagonal[white.first - white.second + N - 1])
	{
		DownDiagonal[white.first + white.second] = true;
		UpDiagonal[white.first - white.second + N - 1] = true;
		FindWhite(White, cnt + 1, idx + 1);
		UpDiagonal[white.first - white.second + N - 1] = false;
		DownDiagonal[white.first + white.second] = false;
	}

    FindWhite(White, cnt, idx + 1);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //합이 짝수면 Black, 홀수면 White
    vector<PII> Black;
    vector<PII> White;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> chess[i][j];

            if(chess[i][j] == 1)
            {
                ((i + j) % 2 == 0) ? Black.emplace_back(i, j) : White.emplace_back(i, j);
            }
        }
    }

    B = Black.size();
    W = White.size();

    FindBlack(Black, 0, 0);
    FindWhite(White, 0, 0);

    cout << ansBlack + ansWhite;

    return 0;
}