[BOJ / C++] 1018 : 체스판 다시 칠하기

링크

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

1018번: 체스판 다시 칠하기

풀이

1. 주어진 보드에서 8x8 크기의 체스판을 뽑아낸다.

2. 뽑아낸 체스판을 이용해서, 가장 왼쪽 위가 검은색으로 시작해야 최소한으로 다시 칠해야 하는지 하얀색으로 시작해야 최소한으로 다시 칠해야 하는지 확인한다.

3. 이렇게 만들 수 있는 체스판을 모두 확인해서 다시 칠해야 하는 정사각형의 최소 개수를 구한다.

단순무식하게 모든 경우의 수를 확인하는 완전 탐색의 기본적인 문제로, 문제가 요구하는 대로 코드를 짜면 되는 간단한 문제다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

typedef long long ll;

int check(vector<string> tmp) {
	/*
	cout << "\n";
	for (string temp : tmp) {
		cout << temp << "\n";
	}
	cout << "\n";
	*/

	int countB = 0;
	int countW = 0;
	char cur;

	/* B로 시작할 경우 */
	for (int i = 0; i < 8; i++) {
		if (i % 2 == 0) cur = 'B';
		else cur = 'W';

		for (int j = 0; j < 8; j++) {
			if (cur == 'B') {
				if (tmp[i][j] == 'W') countB++;
				cur = 'W';
			}
			else if (cur == 'W') {
				if (tmp[i][j] == 'B') countB++;
				cur = 'B';
			}
		}
	}

	/* W로 시작할 경우 */
	for (int i = 0; i < 8; i++) {
		if (i % 2 == 0) cur = 'W';
		else cur = 'B';

		for (int j = 0; j < 8; j++) {
			if (cur == 'B') {
				if (tmp[i][j] == 'W') countW++;
				cur = 'W';
			}
			else if (cur == 'W') {
				if (tmp[i][j] == 'B') countW++;
				cur = 'B';
			}
		}
	}

	if (countB < countW) return countB;
	else return countW;
}

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

	int N, M;
	vector<string> board;
	vector<string> chess;
	int min = 10e10;

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string input;
		cin >> input;
		board.push_back(input);
	}

	// 1. 주어진 board에서 8x8로 잘라낸다
	// 2. 가장 왼쪽 위의 칸이 W면 WBWB... B면 BWBW.. 형태로 구성됐는지 확인
	// 3. 잘못된 부분을 고치는 횟수가 가장 적은 방식을 선택 (가장 왼쪽 위의 칸이 W여야 하는가 B여야 하는가?)

	for (int k = 0; k <= N - 8; k++) {
		for (int l = 0; l <= M - 8; l++) {
			for (int i = 0; i < 8; i++) {
				string tmp = "";
				for (int j = 0; j < 8; j++) {
					tmp += board[k + i][l + j];
				}
				chess.push_back(tmp);
			}

			int current = check(chess);
			if (current < min) min = current;
			chess.clear();
		}
	}

	cout << min;

	return 0;
}