[백준] 알고리즘 C++ 1018번 - 체스판 다시 칠하기문제

문제

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

1018번: 체스판 다시 칠하기

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
char arr[51][51];
char c1[8][8];
char c2[8][8];
string s = "WBWBWBWB";
string s1 = "BWBWBWBW";
int n, m, ans=210000000;
void check(int x, int y) {
	int cnt1 = 0, cnt2 = 0;
	if (x + 8 > n || y + 8 > m) return;
	for (int i = x; i < x+8; i++) {
		for (int j = y; j <y+8; j++) {
			if (arr[i][j] != c1[i-x][j-y]) {
				cnt1++;
			}
			if (arr[i][j] != c2[i-x][j-y]) {
				cnt2++;
			}
		}
	}
	ans = min({ans, cnt1, cnt2 });
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	
	 
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (i % 2 == 0) {
				c1[i][j] = s[j];
				c2[i][j] = s1[j];
			}
			else {
				c1[i][j] = s1[j];
				c2[i][j] = s[j];
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			check(i, j);
		}
	}
	check(0, 0);
	cout << ans;
}

해설

이런 문제는 여러가지 풀어보면 딱 이렇게 풀어야겠다는 감이오게됩니다.

나올 수 있는 경우의 수는 2가지라는 힌트를 문제에서 줬습니다.

왼쪽 위 B로 시작하거나 W로 시작하거나 이거 두개의 경우밖에 없습니다. (비교할 대상)

그러니 모든 경우를 다 탐색해주는 브루트포스로 해결하면 쉽게 해결할 수 있습니다.

우선 초기화 시켜주는 for문을 보면 왼쪽위가 W로 시작하는 배열 C1한개 B로시작하는 배열 C2한개를 초기화 시켜줍니다.

이후 n,m까지 check 함수를 돌면서 모든 경우를 다 비교해보면서 최소로 바꿔야되는 체스판의 개수를 저장하여 출력합니다.