Boj 1799 비숍

1. 문제

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

1799번: 비숍

2. 문제의 요구

체스에서 대각선으로 공격할 수 있는 "비숍"을 서로 공격하지 못하도록

체스판에 배치할 수 있는 최대 개수를 구하여라.

 

3. 풀이

#적용할 알고리즘 : 백트래킹

일단은 단순하게 모든 칸에 대해 각 비숍을 배치할 때 마다

그 대각선 방향에 전에 배치했던 비숍의 유무를 확인하고 없다면

그 자리에 배치하는 방식의 알고리즘을 생각할 수 있다.

하지만 이런 방식은 시간초과가 났다.

여기서 새로운 발상이 필요한데 그것은 바로

#새로운 발상 : 비숍을 놓을 때 체스판의 검은 부분과 흰 부분은 서로 관련이 없다.

비숍을 흰 부분에 놓으면 그 비숍이 공격할 수 있는 곳은 흰 부분 뿐이다.

따라서 체스판의 흰 부분과 검은 부분을 분리하여 따로 백트래킹한다.

이렇게 하면 (10 * 10) = 100 에서 ((5 * 5) * 2) = 50 이 되기 때문에 확실한 이득을 볼 수 있다.

 

4. 코드

#include<iostream>
#include<string>
#include<stack>
#include<tuple>
#include<queue>
#include<algorithm>
#include<bitset>

using namespace std;

#define endl (cout << '\n')

int dx[4] = { 1, -1, 1, -1 };
int dy[4] = { 1, -1, -1, 1 };

int n;

int board[12][12];
bool isUsed[12][12];

vector<pair<int, int>> white;
vector<pair<int, int>> black;

int mx = 0;

//대각선 라인에 다른 비숍이 있는지 확인
//있으면 => 되돌아감
//없으면 => 계속
bool Check(int x, int y)
{
    for (int dir = 0; dir < 4; dir++)
    {
        for (int i = 0; true; i++)
        {
            if (x + i * dx[dir] < 0 || x + i * dx[dir] >= n || y + i * dy[dir] < 0 || y + i * dy[dir] >= n) break;
            //cout << x << ' ' << y << '\n';
            //cout << i << ' ' << dx[dir] << ' ' << dy[dir] << ' ' << x + i * dx[dir] << ' ' << y + i * dy[dir] << '\n';
            if (isUsed[x + i * dx[dir]][y + i * dy[dir]])
            {
                return false;
            }
        }
    }
    return true;
}

//백트래킹
void solve(int cur, vector<pair<int, int>>& color, int start)
{
    mx = max(mx, cur);

    if (cur == color.size()) return;

    for (int i = start; i < color.size(); i++)
    {
        int cx, cy;
        tie(cx, cy) = color[i];

        if (isUsed[cx][cy]) continue;

        if (Check(cx, cy))
        {
            isUsed[cx][cy] = 1;
            solve(cur + 1, color, i + 1);
            isUsed[cx][cy] = 0;
        }
    }
}

bool isWhite[12][12];

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

    cin >> n;

    for (int i = 0; i < n; i += 2) isWhite[0][i] = 1;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            isWhite[i][j] = (isWhite[i - 1][j] ? false : true);
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 1)
            {
            ///화이트 칸과 블랙 칸을 나눠서 벡터에 저장
                if (isWhite[i][j]) white.push_back({i, j});
                else black.push_back({ i, j });
            }
        }
    }

    int ans = 0;

	//화이트 칸과 블랙칸이
	//서로 연관이 없기 때문에 가능하다
	//화이트 칸에서 비숍 배치
    solve(0, white, 0);
    ans += mx;
    mx = 0;
    //블랙 칸에서 비숍 배치
    solve(0, black, 0);
    ans += mx;

    cout << ans;

}

5. 느낀 점

시간을 줄일 방법이 생각이 안나서 결국 답을 찾아봤다.

이런 발상을 좀 더 쉽게 할 수 있도록 계속 생각해야한다.