[BOJ / 백준] 1018번 체스판 다시 칠하기 C++ 문제 풀이

단계별로 풀어보기 - 브루트 포스 단계 - [4단계] 1018번

문제

문제 링크 : www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

입력 복사 : 

> 예제 입력 1

8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW

> 예제 입력 2

10 13 BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB

 

 

 

 

CODE

#include <iostream>
using namespace std;

char arr[51][51];
char white_arr[8][8] = {
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W'
};

char black_arr[8][8] = {
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B'
};

int white_first(int x, int y) {
	int result = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (arr[x + i][y + j] != white_arr[i][j])
				result++;
		}
	}
	return result;
}

int black_first(int x, int y) {
	int result = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (arr[x + i][y + j] != black_arr[i][j])
				result++;
		}
	}
	return result;
}

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

	int n, m, result = 64;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];

	int t_white, t_black;
	for (int i = 0; i <= n - 8; i++) {
		for (int j = 0; j <= m - 8; j++) {
			t_white = white_first(i, j);
			t_black = black_first(i, j);
			if (t_white < t_black) {
				result = (t_white < result) ? t_white : result;
			}
			else {
				result = (t_black < result) ? t_black : result;
			}
		}
	}
	cout << result << '\n';
}

 

 

 

 

풀이

for (int i = 0; i <= n - 8; i++) {
		for (int j = 0; j <= m - 8; j++) {
			t_white = white_first(i, j);
			t_black = black_first(i, j);

모든 8 * 8 크기의 잘라낸 체스판에 대해 다시 칠해야 하는 최소의 수를 계산한다.

 

 

if (t_white < t_black) {
				result = (t_white < result) ? t_white : result;
			}
			else {
				result = (t_black < result) ? t_black : result;
			}

위와 같이 white로 시작하는 경우와 black으로 시작하는 경우를 모두 고려하여 최소값을 구한다.

 

 

 

 

 

결과