[백준 Class 2] 1018번 체스판 C++ 풀이

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

1018번: 체스판 다시 칠하기

문제는 링크를 참고하세요.

 

이번 문제는 실버4 난이도의 체스판 칠하기 입니다.

문제 풀이 알고리즘은 Brute-force(완전탐색) 알고리즘입니다.

이 문제는 문제를 잘 읽어보셔야 합니다. 8X8 크기의 체스판을 만드려고 하는데, 그 이상의 체스판이 주어지면 잘라서 사용합니다. 8X8 크기는 아무데서나 골라도 된다고 하였으므로, 초기 지점에서 자르도록 하겠습니다.

 

먼저 체스판이 흰색으로 시작될 경우와, 검은색으로 시작될 경우를 나누어서 생각해야합니다.

어떤 부분이 최소가 될 지 모르므로, 흰색으로 시작하는 체스판과 검은색으로 시작하는 체스판을 둘다 비교하여, 그 중 최소값을 정답에 저장하면 됩니다.

 

#include <iostream>

using namespace std;

char chess[51][51];
char white_board[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_board[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 cmp_white(int x, int y) {
	int result = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (chess[x + i][y + j] != white_board[i][j])
				result++;
		}
	}
	return result;
}
int cmp_black(int x, int y) {
	int result = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (chess[x + i][y + j] != black_board[i][j])
				result++;
		}
	}
	return result;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, M;
	int answer = 64;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> chess[i][j];
		}
	}
	int cnt_white = 0;
	int cnt_black = 0;
	for (int i = 0; i <= N - 8; i++) {
		for (int j = 0; j <= M - 8; j++) {
			cnt_white = cmp_white(i, j);
			cnt_black = cmp_black(i, j);
			if (cnt_white < cnt_black) {
				if (cnt_white < answer) {
					answer = cnt_white;
				}
			}
			else {
				if (cnt_black < answer)
					answer = cnt_black;
			}
		}
	}
	cout << answer << '\n';
}