[백준/BOJ] 백준 1018번 : 체스판 다시 칠하기

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

완전 탐색(브루트 포스)을 이용해 문제를 해결하였다.

주어진 보드에서 가능한 모든 8*8 형태의 보드를 구해 그중 다시 칠해야 하는 개수의 최솟값을 구했다.

체스판의 형태는 왼쪽 상단이 W이거나 B인 두 경우 뿐이라는 성질을 이용했다.

 

코드

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

int solve(vector<string> board)
{
	int cnt1 = 0;
	int cnt2 = 0;
	//왼쪽 위가 W로 할때 다시칠해야 하는 개수를 구한다
	for(int i=0; i<8; i++)
		for (int j = 0; j < 8; j++)
		{
			if ((i + j) % 2 == 0)
			{
				if (board[i][j] == 'B')
					cnt1++;
			}

			else if ((i + j) % 2 == 1)
			{
				if (board[i][j] == 'W')
					cnt1++;
			}
		}

	//왼쪽 위가 B로 할때 다시칠해야 하는 개수를 구한다
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
		{
			if ((i + j) % 2 == 0)
			{
				if (board[i][j] == 'W')
					cnt2++;
			}

			else if ((i + j) % 2 == 1)
			{
				if (board[i][j] == 'B')
					cnt2++;
			}
		}

	//두 경우중 최솟값을 리턴
	return min(cnt1, cnt2);
}

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

	int n, m;
	vector<string> board;
	string subboard;
	vector<string> tempboard;
	int minresult = 987654321;

	cin >> n >> m;

	//보드를 한줄씩 입력받는다.
	for (int i = 0; i < n; i++)
	{
		cin >> subboard;
		board.push_back(subboard);
	}

	//보드에서 8*8크기의 모든 보드를 검사해서 그중 최솟값을 구한다.
	for(int i=0; i<n-7; i++)
		for (int j = 0; j < m-7; j++)
		{
			tempboard.clear();
			for (int k = i; k < 8 + i; k++)
			{
				subboard = board[k].substr(j, 8);
				tempboard.push_back(subboard);
			}
			minresult = min(minresult, solve(tempboard));
		}

	cout << minresult;

	return 0;
}