체스판 다시 칠하기

import sys


def main():
    input = sys.stdin.readline

    rows, cols = map(int, input().split())
    board = [input().strip() for _ in range(rows)]

    answer = 64

    for y0 in range(rows - 7):
        for x0 in range(cols - 7):
            count = 0
            for dy in range(8):
                for dx in range(8):
                    if board[y0 + dy][x0 + dx] != "BW"[(dy + dx) % 2]:
                        count += 1
            count = min(count, 64 - count)
            answer = min(answer, count)

    print(answer)

main()

문제에서는 행의 수를 $N$, 열의 수를 $M$이라고 표기했는데, 코드와 풀이에서는 각각 $\text{rows}$와 $\text{cols}$로 부르겠습니다. 혼동이 적도록 의미 있는 변수 이름을 사용한 것입니다.

가능한 잘라낼 수 있는 모든 $8 \times 8$ 체스판을 모두 조사해 봅시다. 잘라낼 체스판의 맨 왼쪽 위 칸을 기준 칸이라고 하고, 이 칸의 좌표를 $(y_0, x_0)$라고 합시다. 맨 왼쪽 행($y_0 + 0$)은 $0$ 이상이어야 하고, 맨 오른쪽 행($y_0 + 7$)은 $\text{rows}$보다 작아야 하므로, $y_0$의 범위는 $0 \le y_0 < \text{rows} - 7$입니다. 마찬가지로 $x_0$의 범위는 $0 \le x_0 < \text{cols} - 7$입니다.

기준 칸이 검은색이 되도록 하면서 조건에 맞게 색칠해야 할 칸이 $c$개(코드의 count 변수)라고 합시다. 그러면 반대로 기준 칸을 흰색으로 하면, 색칠해야 할 칸의 개수는 전체 칸의 개수에서 $c$를 뺀 $64 - c$입니다. 둘 중 작은 값 $\min(c, 64 - c)$을 취하고, 모든 기준 칸에 대해서 가장 작은 값을 정답으로 출력하면 됩니다.

$c$의 값은 기준 칸으로부터 $8 \times 8$ 체스판의 각 칸을 조사하면서 계산할 수 있습니다. 기준 칸으로부터 $dy$만큼 아래로, $dx$만큼 오른쪽으로 이동해나가면서, 칸의 색이 목표로하는 색과 다를 때마다 $c$를 1씩 증가시키면 됩니다. 체스판처럼 색깔을 번갈아 가면서 칠할 때, 특정 칸의 색깔은 행과 열의 합이 짝수인 경우와 홀수인 경우로 나눠서 구하면 됩니다. 자주 사용하는 방법으므로 익숙해지면 좋습니다.

이 브루트 포스 알고리즘에서 실행 횟수가 가장 많은 4중 for 문의 반복 횟수는 크게 잡아도 $8^2 * 50^2 = 160\,000$이므로, 충분히 시간제한 내에 종료됩니다.