백준 1018번-체스판 다시 칠하기

문제

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

하지만 지민이는 이 보드가 체스판처럼 검정/흰색 패턴이 번갈아가며 색칠해져있지 않기 때문에 고민에 빠졌다. 따라서 지민이는 8*8크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야 겠다고 생각했다. 당연히 8*8크기는 아무데서나 골라도 된다.

현재 보드의 색이 어떤지 상태가 주어질 때, 지민이가 8*8크기로 자른 뒤에 다시 칠해야하는 정사각형 개수의 최솟값을 구하는 프로그램을 작성하시오.

체스판은 각 정사각형이 검정 또는 흰색이며, 변을 공유하는 두 개의 사각형이 같은 색이 아닐 때 이다. 따라서 위 정의에 의하면 체스판의 색은 항상 두 가지가 가능한데, 하나는 왼쪽 위 코너가 흰색인 것, 검정색인 것 두가지이다.

입력

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

출력

첫째 줄에 지민이가 8*8크기로 자른 뒤에 다시 칠해야하는 정사각형 개수의 최솟값을 출력한다.

 

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

int main() {
	char chess[52][52] = { 0 };
	char chess2[52][52] = {0};
	char chess3[52][52] = { 0 };
	char arr[2]={ 'B','W' };
	char arr2[2]={ 'W','B' };
	int n, m, cnt = 0,cnt2=0,be=0,min_cnt=10000;
	char start;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> chess[i][j];
		}
	}
	for (int l = 0; l < n; l++) {
		chess2[l][0] = arr[l % 2];
	}
	for (int l = 0; l < n; l++) {
		chess3[l][0] = arr2[l % 2];
	}

	for (int k = 0; k < n - 7; k++) {
		for (int z = 0; z < m - 7; z++) {
			cnt = 0;
			cnt2 = 0;
			for (int i = k; i < k+8; i++) {
				for (int j = z; j < z +8; j++) {
					if (j % 2 == z % 2 && chess[i][j] != chess2[i][0])
						cnt++;
					else if (j % 2 == (bool)(z % 2 - 1) && chess[i][j] == chess2[i][0])
						cnt++;
					if (j % 2 == z % 2 && chess[i][j] != chess3[i][0])
						cnt2++;
					else if (j % 2 == (bool)(z % 2 - 1) && chess[i][j] == chess3[i][0])
						cnt2++;
					be=cnt > cnt2 ? cnt2 : cnt;
				}
			}
			if (min_cnt > be)
				min_cnt = be;
		}
	}
	cout << min_cnt;
}

문제를 어렵게 생각해 홀수 짝수를 구분하여 비교하는 등 여러 삽질을 하고 그냥 단순하게 체스판을 만들고 비교하는식으로 풀었다.

첫번째 for문은 입력받는 부분

두번째 세번째 for문은 각각 B부터 시작하는 체스판 W부터 시작하는 체스판 생성

다섯번째 여섯번째는 8X8의 정사각형을 구성하기 위한 경우의 수를 계산하는 for문

일곱번째 여덟번째는 8X8의 공간에서 다시 칠해야하는 갯수를 구하는 부분

B부터 시작하는 체스판과 W부터 시작하는 체스판 중 다시 칠해야하는 갯수가 작은 갯수를 반환

제일 작은 case의 갯수를 출력

테스트 케이스가 다맞았는데 틀렸습니다가 계속 나와 삽질을 엄청하다가 마지막 출력에서 cout의 개행을 지웠더니 해결됐다. ㅂㄷㅂㄷ