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

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

1018번: 체스판 다시 칠하기

백준 온라인저지 1018번 체스판 다시 칠하기 문제입니다.

 

아이디어

흑과 백이 번갈아서 칠해져 있지 않은 체스판을 다시 칠할때 최소로 칠할 수 있게 하는 개수를 구하는 문제입니다.

검정과 흰색을  각각 0과 1로 칠하여 완전탐색으로 풀이했습니다.

 

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

int chess[51][51];

int N, M;
int minIdx = 10004;

void input() {
	char c;
	cin >> N >> M;

	for (int i = 0; i < N; i++) { 
		for (int j = 0; j < M; j++) {
			cin >> c;
			//검정
			if (c == 'B') { 
				chess[i][j] = 0;
				continue;
			};
			//흰색
			chess[i][j] = 1;
		}
	}
}
int check(int x, int y)
{
	int cnt1 = 0;
	int cnt2 = 0;

	for (int i = x; i < x + 8; i++) {
		for (int j = y; j < y + 8; j++) {
			//흰색 시작
			if ((i + j) % 2 == chess[i][j]) 
				cnt1++; 
			//검정 시작
			if ((i + j + 1) % 2 == chess[i][j]) 
				cnt2++; 
		}
	}

	return min(cnt1, cnt2); 
}

void solution() {
	for (int i = 0; i <= N - 8; i++) 
		for (int j = 0; j <= M - 8; j++) 
			if (minIdx > check(i, j)) 
				minIdx = check(i, j); 

	cout << minIdx;
}

int main()
{
	input();
	solution();
}