[코딩테스트]BJ1018번 체스판 다시 칠하기-C++

[문제]

지민에는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져있는 MN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져있고, 나머지는 흰색으로 칠해져있다. 지민이는 이 보드를 잘라서 88 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야한다.구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 2가지 뿐이다.하나는 맨 왼쪽 위의 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져있다는 보장이 없어서, 지민이는 88 크기의 체스판으로 잘라낸 후 몇개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 88 크기는 아무데서나 골라도 된다.지민이가 닫시 칠해야하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다.
둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며,W는 흰색이다.

[출력]

첫째 줄에 지민이가 다시 칠해야하는 정사각형의 개수의 최솟값을 출력한다.

[예제 입력1]

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

[예제 출력 1]

1

[문제풀이]

brute force 방식으로 푸는 문제이다.
이 문제를 풀면서 입력 받은 체스판의 시작 색깔에 따라 구분하여 문제를 해결하려고 해서 시간을 많이 낭비했다. 그러나 이 문제는 정해진 2가지의 방식(흰이 먼저 오는경우, 검이 먼저오는 경우) 을 입력과 상관 없이 모두 고려하여 가장 적은 횟수로 색깔을 바꿀 수 있는지 따져보아야한다.

[코드]

#include<iostream>
#include<algorithm>
using namespace std;

int main() {

	int M, N;
	char chessboard[50][50];
	string whiteFront[8] = {
		{"WBWBWBWB"},
		{"BWBWBWBW"},
		{"WBWBWBWB"},
		{"BWBWBWBW"},
		{"WBWBWBWB"},
		{"BWBWBWBW"},
		{"WBWBWBWB"},
		{"BWBWBWBW"}
	};
	string blackFront[8] = {
		{"BWBWBWBW"},
		{"WBWBWBWB"},
		{"BWBWBWBW"},
		{"WBWBWBWB"},
		{"BWBWBWBW"},
		{"WBWBWBWB"},
		{"BWBWBWBW"},
		{"WBWBWBWB"}
	};
	int min=10000; 
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> chessboard[i][j];
		}
	}

	for (int i = 0; i + 7 < N; i++) {
		for (int j = 0; j + 7 < M; j++) {
			int num1 = 0;
			int num2 = 0;
			int temp;
				for (int n = i, a = 0; n < i + 8; n++, a++) {
					for (int m = j, b = 0; m < j + 8; m++,b++) {
						if (whiteFront[a][b] != chessboard[n][m])num1++;
					}
				}
				for (int n = i, a = 0; n < i + 8; n++, a++) {
					for (int m = j, b = 0; m < j + 8; m++, b++) {
						if (blackFront[a][b] != chessboard[n][m])num2++;
					}
				}
				if (num1 > num2)temp = num2;
				else temp = num1;
				if (min > temp)min = temp;
			
		}
	}
	
	cout << min;
	return 0;
}