BOJ 1018 (체스판 다시 칠하기)

#include <stdio.h>

int min(int a, int b) {
	if (a > b) return b;
	else return a;
}
int main() {
	int N, M;
	int res = 1000000;
	char arr[51][51];
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%s", arr[i]);
	}
	
	for (int i = 0; i < N - 7; i++) {
		for (int j = 0; j < M - 7; j++) {
			int cnt = 0;
			int num = 0;
			for (int k = i; k < 8 + i; k++) {
				for (int l = j; l < 8 + j; l++) {
					if (arr[i][j] == 'W') {
						if (num % 2 == 0 && arr[k][l] == 'B') { cnt++; }
						if (num % 2 != 0 && arr[k][l] == 'W') { cnt++; }
					}
					else {
						if (num % 2 == 0 && arr[k][l] == 'W') { cnt++; }
						if (num % 2 != 0 && arr[k][l] == 'B') { cnt++; }

					}
					num++;
				}
				num--;
			}
			res = min(res, cnt);
			res = min(res, 64 - cnt);
		}
	}
	printf("%d", res);

	return  0;
}

일단 처음에, 칠하는 최솟값이 나오는 8*8 체스판의 시작점을 구해야하나 고민했는데 문제 분 브루트포스고 시작점을 구할 엄두가 안나서 (0,0)에서 8*8로 가능한 곳 까지 칠해야 하는 경우를 구하고 최솟값을 계산했다. 삽질했던 부분은, x+y가 홀수인가 짝수인가로 cnt를 증가시켰는데, 꼭 0,0일때만 계산하는게 아니라 내가 짠 코드는 (0,0), (0,1), (0,2) ... 이런식으로 이동하면서 칠해야 하는 부분을 계산하기 때문에 이 방식을 불가능했다. 그래서 num이란 변수를 선언해서 이를 해결했다. 두 번째는, res = min(res, 64-cnt); 를 추가한 부분이다. 이 부분을 왜 추가해야 하는지 처음에는 몰랐는데 내 코드는 가장 맨 위 왼쪽은 고정되있는 상태로 칠할 부분을 계산하기 때문에 반전되어 있을 때, 더 최솟값을 계산할 수 있다. 만약에 계산했는데 63이 나왔다면 그 반대의 경우로는 1이 최솟값이 되는 것이다.

다른 방법으로도 이 문제를 해결할 수 있다. 미리 가장 맨 왼쪽이 'B'일 경우와 'W'일 경우의 8*8 체스판을 만들고 두 개다 비교하고 각각의 cnt 변수를 증가시킨다. 이렇게 구현하면 위의 코드처럼 64 - cnt를 할 필요가 없다. 소스코드는 따로 공개하진 않겠다.