백준 링크 : https://www.acmicpc.net/problem/1018

문제 개요

체스판은 검은색, 흰색의 정사각형이 번갈아가면서 나온다는 특징이 있는데, N x M의 체스판이 주어지면 이를 8 X 8의 검은색과 흰색이 번갈아나오는 정상적인 체스판으로 바꾸기 위해서 최소한의 몇 번의 색칠이 필요한지 구하는 문젱디ㅏ.

아이디어

• W부터 시작하는 8 X 8 문자열 배열을 만든다. → WB 배열
• B부터 시작하는 8 X 8 문자열 배열을 만든다. → BW 배열
• 입력된 배열과 WB배열과 BW배열을 브루트포스를 통해 비교하고 이 과정에서 최소값을 갱신해나간다.

주의사항

• 브루트포스로 하게 될 경우 4중 for이 나오게 되는데, 입력값이 50보다 작은 자연수라는 조건에 의해 이는 문제가 되지 않는다는 것을 알고, 구현을 하면 된다.

코드

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
int height, width, mn = INT_MAX;
char c;
string WB[8] = {
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW"
};

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

string s[54];
int main()
{
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> height >> width;
	
	for(int i = 0; i < height; i++)
	{
		cin >> s[i];
	}

	for(int i = 0 ; i <= height - 8; i++)
	{
		for(int j = 0; j <= width - 8; j++)
		{
			int WB_cnt = 0;
			int BW_cnt = 0;
			for(int k = i; k < i + 8; k++)
			{
				for(int l = j; l < j + 8; l++)
				{
					if(s[k][l] != WB[k - i][l - j]) WB_cnt++;
					if(s[k][l] != BW[k - i][l - j]) BW_cnt++;
				}
			}
			
			mn = min(mn, min(WB_cnt, BW_cnt));
		}
	}
	
	cout << mn;

  return 0;
}

후기

4중 반복문에 조건식도 복잡하다보니 곧바로 구현이 안됐었다.

해결 방안으로 직접 그려보고 조건식에 어떤 값들이 들어가야 하는지 손으로 써보니 점점 식이 명확해져갔다.

역시 곧바로 구현하는 것보다는 도식화를 통해 모든 것을 명확히하고 코딩을 진행하는 것이 결과적으로 시간을 절약하는 것 같다.