[백준] 1799 - 비숍

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

1799번: 비숍

 

이 문제를 처음 풀 때는, 모든 경우의 수를 생각하였다.

이렇게 순수하게 접근할 경우, O(2 ^ 100)으로 10초라는 시간에도 통과하지 못한다.

 

여기서 비숍의 특징을 생각해보자.

만약 비숍이 체스판의 흑색 위치에 있다면, 체스판의 백색 위치에 갈 수 있는 방법은 없다.

마찬가지로

만약 비숍이 체스판의 백색 위치에 있다면, 체스판의 흑색 위치에 갈 수 있는 방법은 없다.

 

따라서 비숍은 현재 위치의 색이 있는 칸에만 도달할 수 있다.

 

그렇다면 시간 복잡도를 계산해보자.

흑과 백을 나누어서 풀 경우, 단순하게 생각해보면 O(2^(n * n / 2))가 될 것이다.

그렇다면 n = 10일 경우, 2 ^ 50 => TLE가 날 것이다.

하지만 그렇지 않다.

 

바로 branch and bound, 분기 한정 법을 이용하면 O(2^((n/2)*(n/2)))으로 줄일 수 있다.

왜냐하면 비숍은 대각선 공격만 가능하기 때문이다.

즉, (0, 0)에 비숍을 놓았을 경우에는 (1, 1), (2, 2)... (n - 1, n - 1)의 경우를 생각할 필요가 없다는 것이다.

 

위 그림에서 흑색칸과 백색 칸은 각각 5, 4개이지만 대각선 체크를 통해 갈 수 있는 곳과 갈 수 없는 곳을 알 수 있다면, 탐색 칸의 최대 개수는 각각 2, 2개가 된다.

 

사실 이 시간복잡도 O(2^((n/2)*(n/2)))도 대략적인 것이라, 증명할 수 있으면 좋겠으나, 그것까진 하지 못했다.

 

이제 문제 풀이에 들어가 보자.

 

우리가 해야 할 것은 대각선 체크만 완료하면 된다.

 

/ 대각선을 체크하는 배열을 l이라 하자.

\ 대각선을 체크하는 배열을 r이라 하자.

 

각 대각선 배열은 n = 10일 때 최대 19개가 생길 수 있다.

 

현재 위치를 (i, j)라 할 때,

/ 대각선은 l[i + j]로 체크할 수 있다.

\ 대각선은 r[j - i + n - 1]로 체크할 수 있다.

 

#include <iostream>
using namespace std;

int n, ans[2], map[10][10], lo[20], ro[20];

void go(int r, int c, int cnt, int color)
{
    if (c >= n)
    {
        r++;
        if (c % 2 == 0)
        {
            c = 1;
        }
        else
        {
            c = 0;
        }
    }
    if (r >= n)
    {
        ans[color] = max(ans[color], cnt);
        return;
    }

    if (map[r][c] && !lo[c - r + n - 1] && !ro[c + r])
    {
        lo[c - r + n - 1] = 1;
        ro[c + r] = 1;
        go(r, c + 2, cnt + 1, color);
        lo[c - r + n - 1] = 0;
        ro[c + r] = 0;
    }
    go(r, c + 2, cnt, color);
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
        }
    }

    go(0, 0, 0, 0);
    go(0, 1, 0, 1);

    cout << ans[0] + ans[1];
}