백준 1799번 비숍 C++ (골드1)

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

 

대각선으로만 이동할 수 있는 비숍 말들을 영역이 겹치지 않게 배치할 수 있는 최대의 수를 구하는 문제이다.

처음에 배치할 수 있는 영역은 제한되어있고, 배치를 못하는곳에 움직이는 것은 가능하다.

 

우선 직관적으로 백트래킹으로 접근하여 배치가 가능한 영역들을 저장하고 저장한 영역들에 대해 백트래킹을 돌려주었다.

한번 배치한 영역은 4가지 대각선 방향에 다른 말이 배치할 수 없도록 표시를 해두고 저장해뒀다가, 돌아올때는 표시한 영역들을 다시 원상태로 돌려주었다.

 

하지만 역시 골드1이라그런지 이런 단순한 방법으로는 풀리지 않았고 시간초과가 났다.

 

계속 생각해봤는데도 마땅한 방법이 생각나지 않아서 질문 게시판을 한번 들어가봤는데 흑색과 백색으로 나누라는 얘기가 있었다.

아니 문제에는 다 똑같은 말이고 그런말이 없는데 이게 대체 무슨소리지 하고 곰곰히 생각해보다가 한가지 깨달음을 얻었다.

비숍 말들은 대각선으로만 움직일 수 있고, 그렇다면 처음 배치되는 위치에 따라서 체스판의 절반의 공간과는 완전히 분리된다. 

흑색 위치에 배치된다면 흑색 위치로만 움직일 수 있고, 흑색 위치에 있는 비숍에만 영향을 받는다. 백색도 마찬가지이다.

그래서 처음 체스판 입력을 받을때 row + col이 짝수인 경우와 홀수인 경우를 분리하여 저장했고, 백트래킹을 두변 돌려서 서로의 최대값을 합쳐 문제를 해결하였다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n;
int dRow[4] = { -1,1,1,-1 };
int dCol[4] = { 1,1,-1,-1 };

int ans1 = 0;
int ans2 = 0;
vector<vector<int>> board;
vector<pair<int, int>> placePoses1;
vector<pair<int, int>> placePoses2;
map<pair<int, int>, bool> canPlace;

vector<pair<int,int>> SetPlacePossible(int row, int col, bool possible)
{
    vector<pair<int, int>> poses;
    canPlace[{row, col}] = possible;
    poses.push_back({ row,col });
    for (int i = 0; i < 4; i++)
    {
        int nextRow = row + dRow[i];
        int nextCol = col + dCol[i];
        while ((nextRow >= 0 && nextRow < n) && (nextCol >= 0 && nextCol < n))
        {
            if (canPlace[{nextRow, nextCol}] == possible)
            {
                nextRow += dRow[i];
                nextCol += dCol[i];
                continue;
            }
            canPlace[{nextRow, nextCol}] = possible;
            poses.push_back({ nextRow,nextCol });
            nextRow += dRow[i];
            nextCol += dCol[i];
        }
    }
    return poses;
}

void BT1(int idx, int count) {
    for (int i = idx; i < placePoses1.size(); i++)
    {
        pair<int, int> curr = placePoses1[i];
        if (canPlace[{curr.first, curr.second}] == false) continue;
        vector<pair<int, int>> poses;
        poses = SetPlacePossible(curr.first, curr.second, false);
        BT1(i + 1, count + 1);
        for (auto a : poses)
        {
            canPlace[{a.first, a.second}] = true;
        }
    }
    ans1 = max(ans1, count);
}

void BT2(int idx, int count) {
    for (int i = idx; i < placePoses2.size(); i++)
    {
        pair<int, int> curr = placePoses2[i];
        if (canPlace[{curr.first, curr.second}] == false) continue;
        vector<pair<int, int>> poses;
        poses = SetPlacePossible(curr.first, curr.second, false);
        BT2(i + 1, count + 1);
        for (auto a : poses)
        {
            canPlace[{a.first, a.second}] = true;
        }
    }
    ans2 = max(ans2, count);
}

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

    cin >> n;
    board = vector<vector<int>>(n, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 1)
            {
                if ((i + j) % 2 == 0)
                {
                    placePoses1.push_back({ i,j });
                    canPlace.insert({ {i,j},true });
                }
                else 
                {
                    placePoses2.push_back({ i,j });
                    canPlace.insert({ {i,j},true });
                }
            }
        }
    }
    BT1(0, 0);
    BT2(0, 0);
    cout << ans1 + ans2;
}