[1018] 체스판 다시 칠하기

문제

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

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

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

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

입력

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

출력

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

예제 입력

8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW

예제 출력

1

---

문제 풀이

체스판의 모습은 흰색으로 시작하는 체스판과, 검은색으로 시작하는 체스판의 경우밖에 없다.

그래서 각 경우를 변수로 지정해놓고 같은지 아닌지 판단하면 된다.

/* 다시 칠해야 하는 정사각형의 최소 개수 */
/* 2019-07-09 체스판 다시 칠하기 */

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

const int white[8][8] = {
	{ 0,1,0,1,0,1,0,1 },
	{ 1,0,1,0,1,0,1,0 },
	{ 0,1,0,1,0,1,0,1 },
	{ 1,0,1,0,1,0,1,0 },
	{ 0,1,0,1,0,1,0,1 },
	{ 1,0,1,0,1,0,1,0 },
	{ 0,1,0,1,0,1,0,1 },
	{ 1,0,1,0,1,0,1,0 }
};

const int black[8][8] = {
	{ 1,0,1,0,1,0,1,0 },
	{ 0,1,0,1,0,1,0,1 },
	{ 1,0,1,0,1,0,1,0 },
	{ 0,1,0,1,0,1,0,1 },
	{ 1,0,1,0,1,0,1,0 },
	{ 0,1,0,1,0,1,0,1 },
	{ 1,0,1,0,1,0,1,0 },
	{ 0,1,0,1,0,1,0,1 }
};

int small = 987654;

bool check(vector<vector<int> >board, int y, int x) {
	int cnt = 0;
	
	//보드판을 벗어나는가?
	if (y+7 >= board.size() || x+7 >= board[0].size()) {
		return false;
	}

	int ny = y;
	int nx = x;

	for (int i = 0; i < 8; i++) {
		nx = x;
		for (int j = 0; j < 8; j++) {
			if (white[i][j] != board[ny][nx]) cnt++;
			if(nx!=board[0].size()-1) nx++;
		}
		if (ny != board.size()-1) ny++;
	}
	//cout << y <<" " << x <<" "<<cnt <<endl;
	if (small > cnt) small = cnt;
	
	ny = y;
	cnt = 0;
	for (int i = 0; i < 8; i++) {
		nx = x;
		for (int j = 0; j < 8; j++) {
			if (black[i][j] != board[ny][nx]) cnt++;
			if (nx != board[0].size()-1)nx++;
		}
		if (ny != board.size()-1)ny++;
	}
	//cout << y << " " << x << " " << cnt << endl;
	if (small > cnt) small = cnt;

	return true;
}

int main() {
	int m, n;
	char temp;

	cin >> m >> n;
	vector<vector<int> > board(m, vector<int>(n, 0));

	//보드판 만들기
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> temp;
			if (temp == 'B') board[i][j] = 1; // 검은 칸은 1로 저장
		}
	}

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			check(board, i, j);
		}
	}
	cout << small;

}

따라서 지민이는 8*8크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야 겠다고 생각했다. 당연히 8*8크기는 아무데서나 골라도 된다.

m*n의 체스판을 8*8로 잘라내고 그 상태에서 몇 개의 정사각형을 다시 칠할 것인지 판단해야 하기 때문에 이중 포문을 이용해서 모든 칸에서 8*8로 잘라내는 시나리오를 그렸다.

바로 check 함수에서 잘라낸 8*8 보드판이 범위를 벗어난지 판단하고, 몇 개의 정사각형을 다시 칠해야 하는지도 판별한다. 흰색으로 시작하는 체스판과 검은색으로 시작하는 체스판 모두를 비교해 가장 적게 칠하는 수를 알아낸다.