백준 | 1018

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

검은색(B)과 흰색(W)로 칠해진 M x N 크기의 체스판이 주어진다.

주어진 체스판을 잘라 8 x 8 크기의 체스판으로 만들려고 하는데,
이웃한 변이 서로 다른 색이어야 한다.

이때, 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 문제이다.

지민이가 만들고자 하는 체스판은 아래 2가지 경우만 존재한다.

1) white case(맨 왼쪽 위 칸이 흰색인 경우)
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

2) black case(맨 왼쪽 위 칸이 검은색인 경우)
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

2가지 경우의 공통점은..
8 X 8 체스판의 좌표 (x, y)가 (0, 0)부터 시작된다고 했을 때,
x + y가 짝수인 좌표는 해당 케이스의 맨 왼쪽 위 칸의 색과 일치한다는 점이다.

그래서 x + y가 찍수인 경우와 홀수인 경우로 나누고,
각 경우에서 white case, black case를 각각 고려하여 문제를 풀 수 있다.

1) x + y가 짝수
(1) white case에선 흰색이어야 하므로, 이 좌표가 흰색이 아니면 색칠해야 한다.
(2) black case에선 검은색이어야 하므로, 이 좌표가 검은색이 아니면 색칠해야 한다.

2) x + y가 홀수
(1) white case에선 검은색이어야 하므로, 이 좌표가 검은색이 아니면 색칠해야 한다.
(2) black case에선 흰색이어야 하므로, 이 좌표가 흰색이 아니면 색칠해야 한다.

코드(정답)는 다음과 같다.

import sys


# 다시 색칠해야 하는 정사각형 개수의 최솟값을 구하는 함수
def make_chessboard(board, n, m):
    min_cnt = 64 + 1
    
    for i in range(n - 7):
        for j in range(m - 7):
            w_cnt, b_cnt = 0, 0
            for x in range(8):
                for y in range(8):
                    if ((x + y) % 2) == 0:
                        # white case
                        if board[i + x][j + y] != "W":
                            w_cnt += 1
                        # black case
                        if board[i + x][j + y] != "B":
                            b_cnt += 1
                    else:
                        # white case
                        if board[i + x][j + y] != "B":
                            w_cnt += 1
                        # black case
                        if board[i + x][j + y] != "W":
                            b_cnt += 1

            min_cnt = min(min_cnt, w_cnt, b_cnt)
    
    return min_cnt


# 입력
n, m = map(int, sys.stdin.readline().split())
board = [sys.stdin.readline().strip() for _ in range(n)]

print(make_chessboard(board, n, m))