[백준/C++] 1018 체스판 다시 칠하기

1018 체스판 다시 칠하기

#include <bits/stdc++.h>
using namespace std;

string WB[8] =
{
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
};

string BW[8] =
{
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
};

string board[50];
int cntWB(int x, int y);
int cntBW(int x, int y);

int main() 
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int n, m;
	cin >> n >> m;
	cin.ignore();

	for (int i = 0; i < n; ++i)
		getline(cin, board[i]);

	int min_val = 65;

	for (int i = 0; i + 8 <= n; ++i)
	{
		for (int j = 0; j + 8 <= m; ++j)
		{
			int temp = min(cntWB(i, j), cntBW(i, j));
			if (temp < min_val)
				min_val = temp;
		}
	}

	cout << min_val;
	return 0;
}

int cntWB(int x, int y)
{
	int cnt = 0;
	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			if (board[x + i][y + j] != WB[i][j])
				++cnt;
		}
	}
	return cnt;
}

int cntBW(int x, int y)
{
	int cnt = 0;
	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			if (board[x + i][y + j] != BW[i][j])
				++cnt;
		}
	}
	return cnt;
}

• 브루트포스 문제

1. 비교할 체스판 배열과 board 배열을 만들어야 한다.
   • 체스판은 맨 왼쪽 윗 칸이 흰색인 경우, 검은색인 경우 두 가지가 있다.
   • 따라서 W로 시작하는 배열과 B로 시작하는 8*8배열을 미리 만들어준다.
   • 입력받은 mn 보드는 최대 5050 크기로 만들어 준다.
2. 새로 칠해야 할 칸의 수를 구하는 함수를 구현한다.
   • 맨 왼쪽이 B인 경우와 W인 경우 두 가지를 모두 고려해서 구해야한다.
   • 따라서 두 가지를 구한다음 min함수를 통해 최솟값을 구해야한다.