[BAEKJOON] 1018

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[sliver4, 1018 체스판 다시칠하기] - 브루트포스

핵심은 체스판을 칠하는 것이다. 8x8 정사각형을 자르는 기준인 좌측 상단 꼭짓점을 기준으로 했을 때,
기준의 색을 변경하지 않고 체스판을 다시 칠하는 것과
기준의 색을 변경하고 체스판을 다시 칠하는 것을 고려하여 모든 경우의 수를 판단해주어야 한다.
  
기준과 다름을 판단하는 원리는, 체스판의 규칙성에 존재한다.
체스판은 모든 색상이 대각선으로 일치하며, 상하좌우로 나와는 다른 색을 지닌 칸이 존재한다.
이 규칙들을 활용한다.
  
보드의 (y,x)를 기준으로 (y-1,x), (y,x-1), (y+1,x), (y,x+1)은 다른 색이 존재하므로
(y+x) mod 2의 결과값은 (y-1,x), (y,x-1), (y+1,x), (y,x+1)에 mod 2한 값과 다르다.
따라서, 기준과 mod 2의 결과값이 같은 칸은 색상이 일치하고, 다른 칸은 색상이 불일치 해야 한다.
그러므로, 결과값이 같은 칸이 색상이 불일치하고, 다른 칸이 색상이 일치한다면 그 칸은 다시 칠해야 하는 칸이 된다.

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

#define MAX 51

int H, W, answer = 987654321;
char map[MAX][MAX];

void checkBoard(int sy, int sx);
void rePaint(int sy, int sx, char color);

int main() {
	scanf("%d %d", &H, &W);
	for (int h = 0; h < H; h++)
		scanf("%s", &map[h]);

	for (int i = 0; i <= H - 8; i++) {
		for (int j = 0; j <= W - 8; j++) {
			checkBoard(i, j);
		}
	}
	printf("%d", answer);
}

void checkBoard(int y, int x) {	
	rePaint(y, x, map[y][x]);
	rePaint(y, x, map[y][x] == 'W' ? 'B' : 'W');
}

void rePaint(int sy, int sx, char color) {
	int type = (sy + sx) % 2;
	int cnt = 0;
	for (int i = sy; i < sy + 8; i++) {
		for (int j = sx; j < sx + 8; j++) {
			if ((i + j) % 2 == type && color == map[i][j]) continue;
			if ((i + j) % 2 != type && color != map[i][j]) continue;
			cnt += 1;
		}
	}
	answer = answer < cnt ? answer : cnt;
}