N*N 크기의 체스판에 비숍을 놓을 수 있는 칸과 놓을 수 없는 칸이 구분되어 주어질 때, 비숍을 최대로 놓을 수 있는 경우 비숍의 개수를 구하는 문제입니다. ⑤ 9663 - N-Queen 문제와 매우 비슷한 문제이고, 푸는 알고리즘의 방식도 비슷합니다. 백트래킹을 사용하여 풀어야 하는데, 단순한 백트래킹으로는 아래의 예시에 의해 당신의 코드가 뚜까맞습니다시간 초과가 납니다.
Input:
10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
Output:
18
이를 해결할 수 있는 방법은 이 문제를 두 독립적인 문제로 분할하는 것입니다. 퀸의 경우는 다른 모든 퀸에게 영향을 줄 수 있었으나, 비숍은 그렇지 않습니다. 체스판의 검은 칸 위에 있는 비숍은 검은 칸 위에 있는 비숍에게만 영향을 주고, 흰 칸 위에 있는 비숍은 흰 칸 위에 있는 비숍에게만 영향을 줍니다. 즉, 검은 칸에 대한 경우와 흰 칸에 대한 경우를 구하여 더하면 되는 것입니다. 이렇게 하면 탐색하는 경우가 매우 줄어드므로($N^2!\rightarrow(\frac{N^2}{2})!$) 여기에 걸리는 시간 또한 매우 줄어듭니다. 이렇게 하면 여유로운 시간 내에 정답을 맞출 수 있습니다.
PS알못 OrbitHv의 PS