pushback

\(N, M\)이 최대 50이기 때문에 브루트 포스로 충분히 해결 가능한 문제로 보인다.

맨 왼쪽 위칸이 검은색인 경우와 흰색인 경우의 (8x8)체스판을 미리 준비해놓고, NxM체스판 위를 돌아다니며 미리 준비해둔 8x8 체스판과 몇 칸이 다른지 확인해보자. 가장 적은 칸이 다른 경우가 답이 된다.

이 아이디어가 가능한지 시간 복잡도를 생각해보자.

최악의 경우로 (50x50)크기의 체스판에서 (42x42)개의 (8x8)체스판을 뽑아낼 수 있고, 체스판을 한번 뽑아낼 때마다 2x64번의 비교가 필요하다. 따라서 최대 42x42x2x64(=225,792)번의 연산만 하면 되기 때문에 브루트 포스가 가능하다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

char chess[50][50];
char b[50][50]; // 맨 왼쪽 위 칸이 black인 경우
char w[50][50]; // 맨 왼쪽 위 칸이 white인 경우
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    string s;

    int ans = 987654321;

    for (int i = 0; i < N; i++) {
        cin >> s;
        for (int j = 0; j < M; j++) {
            chess[i][j] = s[j];
            // 미리 b배열과 w배열 채워놓기
            if ((i + j) % 2 == 0) {
                b[i][j] = 'B';
                w[i][j] = 'W';
            }
            else {
                b[i][j] = 'W';
                w[i][j] = 'B';
            }
        }
    }

    // 8x8로 잘라서 비교 
    for (int i = 0; i < N - 7; i++) for (int j = 0; j < M - 7; j++) {
        int tmpB = 0, tmpW = 0;

        for (int x = i; x < i + 8; x++) for (int y = j; y < j + 8; y++) {
            if (chess[x][y] != b[x][y]) tmpB++;
            if (chess[x][y] != w[x][y]) tmpW++;
        }

        ans = min({ ans, tmpB, tmpW }); // min이 자주 수행되는 경우엔 2개씩 비교하는게 더 좋다.
        
    }

    cout << ans << '\n';

    return 0;
}