※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
비숍이 놓인 자리를 기준으로 왼쪽 대각선, 오른쪽 대각선은 다른 비숍을 둘 수 없습니다. 그러므로 비숍을 놓을 수 있는 자리를 기준으로 왼쪽 대각선, 오른쪽 대각선에 각각의 id를 부여한 뒤, 해당 자리의 왼쪽 대각선과 오른쪽 대각선을 그래프로 연결 시킵니다.
이 때 조심할 것은, 대각선 id의 최댓값은 100*100 칸의 체스칸에 체크무늬로 장애물이 놓여 있을 때 5000까지 가능하다는 점입니다. 인접 행렬을 통해 v[5000][5000] 칸의 배열을 잡는 것 보다는, 2차원 벡터를 활용한 인접 리스트를 이용하는 것이 좋습니다.
각 자리에 대해 왼쪽 대각선, 오른쪽 대각선의 id를 그래프로 연결 시킨 다음 보면, 결국 이 그래프에서 최고로 매칭시킬 수 있는 대각선의 수가 비숍을 놓을 수 있는 수가 되므로, 최대 이분 매칭을 찾으면 정답을 도출할 수 있습니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
int n, m, ans, p, b[101][101], id[2][101][101];
vector<vector<int> >g;
vector<int> match;
vector<bool> visited;
bool mbm(int n)
{
if (visited[n]) return false;
visited[n] = true;
for (auto it : g[n])
{
if (match[it] == -1 || mbm(match[it]))
{
match[it] = n;
return true;
}
}
return false;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
b[x][y] = true;
}
for (int i = 0; i < 2; i++)
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
{
if (!b[x][y] && !id[i][x][y])
{
id[i][x][y] = ++p;
int tx = x, ty = y, dir = !i ? -1 : 1;
while (1)
{
tx++, ty += dir;
if (tx < 1 || ty < 1 || tx > n || ty > n || b[tx][ty]) break;
id[i][tx][ty] = p;
}
}
}
g.resize(p + 1);
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
if (!b[x][y])
g[id[0][x][y]].push_back(id[1][x][y]);
match = vector<int>(p + 1, -1);
for (int i = 1; i <= p; i++)
{
visited = vector<bool>(p + 1, false);
if (mbm(i)) ans++;
}
cout << ans;
}