[Baekjoon] 1018 - 체스판 다시 칠하기 (C++)

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

1018번: 체스판 다시 칠하기

M × N 크기의 보드가 주어집니다. 이를 8 × 8 크기의 정사각형으로 잘라서 색을 칠했을 때 다시 칠해야 하는 정사각형의 최소 개수를 구하는 문제입니다.

 

입력으로 들어오는 N과 M의 크기가 최대 50인 것을 보고 브루트 포스로 모든 경우의 수를 다 고려해서 풀면 될 것 같다는 생각이 들었습니다. 8 × 8 크기로 자른 보드에서 첫 번째 칸의 색이 하얀색인 경우와 검은색인 경우에 대해 개수를 구하고 최솟값을 계산하는 방식으로 풀었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int getSquareCount(const vector<vector<char>>& board, int startX, int startY)
{
	int whiteCount = 0;
	int blackCount = 0;

	// 첫 번째 칸의 색을 기준으로 칠해야 할 정사각형의 개수를 계산
	for (int y = 0; y < 8; y++) {
		for (int x = 0; x < 8; x++) {
			char nowColor = board[startY + y][startX + x];

			if (y % 2) {
				if (x % 2) {
					whiteCount += nowColor == 'B';
					blackCount += nowColor == 'W';
				}
				else {
					whiteCount += nowColor == 'W';
					blackCount += nowColor == 'B';
				}
			}
			else {
				if (x % 2) {
					whiteCount += nowColor == 'W';
					blackCount += nowColor == 'B';
				}
				else {
					whiteCount += nowColor == 'B';
					blackCount += nowColor == 'W';
				}
			}
		}
	}

	return min(whiteCount, blackCount);
}

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

	int n, m;
	cin >> n >> m;

	vector<vector<char>> board(n, vector<char>(m));
	int squareCount = INT_MAX;

	// 보드 상태 입력
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cin >> board[y][x];
		}
	}

	// 모든 경우의 수를 전부 확인 (완전 탐색)
	for (int startY = 0; startY < n - 7; startY++) {
		for (int startX = 0; startX < m - 7; startX++) {
			squareCount = min(squareCount, getSquareCount(board, startX, startY));
		}
	}

	cout << squareCount << "\n";
	return 0;
}