(C++) 백준 1018번 - 체스판 다시 칠하기

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

문제

> MN개의 단위 정사각형으로 나누어져있는 MxN크기의 보드를 찾았다.
> 검은색, 흰색으로 칠해져있는데 이 보드를 잘라 8x8로 만들려고한다.
> 색을 번갈아 가며 칠해야 한다. 즉, 변을 공유하는 사각형은 서로 다른 색이어야함.
> 체스판을 아무데서나 8x8로 자른 후 다시 칠해야 하는 최소의 수를 구해라.

접근

브루트포스 알고리즘을 이용해 가능한 경우의 모든 체스판을 구한다.
각각의 체스판을 좌상단이 검은색, 흰색으로 시작하는 체스판일 때의 경우와 비교해 둘중에 더 작은 색칠 수를 구한다.
앞에서 나온 수와 가능한 체스판들의 경우와 비교해 더 작은 값을 구한다.

문제해결

> 좌상단이 검은색, 흰색으로 시작하는 체스판을 먼저 정의해준다.
> 색칠해야하는 칸의 수를 구하는 Comp함수를 정의한다. 앞서 정의한 검은색, 흰색 체스판과 입력으로 들어온 체스판을 각각 비교해 다른 부분의 수(새로 칠해야하는 칸)를 누적한다.
두 수를 비교해 더 작은걸 선택한다. 어떤 색으로 시작하는 판으로 새로 칠해 만들어야 더 적게 칠하는지를 구하는 과정이다.
> 메인 함수에서 체스판을 입력받고 입력받은 체스판을 0,0에서 시작해 모든 경우로 자른다. 자르면서 나온 체스판을 Comp함수에 넣는다.
> 나온 값은 해당 체스판의 최소로 칠해야하는 수이다. 이 수를 최악의 경우(모든칸을 다 다시칠해야 하는 경우와 비교해 최소값 변수에 넣는다.)
> 다음 체스판의 경우를 각각 구하며 위 과정을 반복한다. 최종으로 나온 수를 출력한다.

코드

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

vector<string> Black =
{
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB"
};
vector<string> White =
{
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW"
};
int Comp(vector<string> vec1)
{
	int Bcnt = 0, Wcnt = 0;
	
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			if (vec1[i][j] != Black[i][j]) Bcnt++;
			if (vec1[i][j] != White[i][j]) Wcnt++;
		}
	}
	int cnt = min(Bcnt, Wcnt);
	return cnt;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, M;
	cin >> N >> M;
	int MinC = 64;
	vector<string> chess(N);
	for (int i = 0; i < N; i++) cin >> chess[i];

	for (int i = 0; i + 7 < N; i++) //행
	{
		for (int t = 0; t + 7 < M; t++) // 열
		{
			vector<string> compchess(8);
			for (int j = 0; j < 8; j++) //행
			{
				compchess[j] = chess[j+i].substr(t, 8);
			}
			MinC = min(MinC, Comp(compchess));
		}
	}
	cout << MinC << '\n';
}

후기

가능한 모든 경우로 체스판을 쪼개는 부분(메인함수 내부)이 생각보다 반복문의 연산 순서가 복잡해 새로 만들어진 compchess의 인덱스를 설정해주는데가 어려웠다.