1018번: 체스판 다시 칠하기

M x N 크기의 체스판의 각 칸은 B 또는 W로 채워져 있다.

 

이것을 8 x 8 크기로 B, W, B, W또는 W, B, W, B로 다시 칠하려고 할 때  고쳐야 하는 최소 칸의 개수를 구하는 문제

---

1. x, y 좌표 축 설정

n을 y축, m을 x축이라 하면 이차원 배열 board[n][m]은 다음과 같이 채울 수 있다.

for (int y = 0; i < n; i++) {
		for (int x = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}

 

2. 특정 원소부터 시작해 8 x 8 크기에서 다시 칠해야 하는 칸의 개수를 구하는 함수

다음 이차원 배열의 성질을 이용해 체스판의 특정 칸에 접근할 수 있다.

(y + x) % 2 == 0, (y + x) % 2 == 1로 위치를 구분할 수 있다.

 

첫 칸이 W인 경우와 B인 경우의 값을 구하기 위해 매개변수 c를 사용한다.

 

다시 칠해야 하는 칸의 개수를 구한 후 최솟값 ans를 대체한다.

void checkMin(char c, int sy, int sx) {
	int cnt = 0;
	for (int y = sy; y < sy + 8; y++) {
		for (int x = sx; x < sx + 8; x++) {
			if ((y + x) % 2 == 0) {
				if (board[y][x] != c) cnt++;
			}
			else {
				if (board[y][x] == c) cnt++;
			}
		}
	}
	if (cnt < ans) ans = cnt;
}

3. 주어진 체스판의 크기에 맞게 checkMin 함수를 실행한다.

첫 칸이 B인 경우와 W인 경우 모두에 대해 함수를 실행한다.

🔑 조건에 맞는 모든 칸에 대해 풀이를 적용하기 위해 알맞은 함수 signature를 설계한다.
🔑 풀이를 위해 체스판을 나눌 수 있는 방법을 찾는다.

---

#include <bits/stdc++.h>
using namespace std;

int n, m, ans = 64;
char board[50][50];

void checkMin(char c, int sy, int sx) {
	int cnt = 0;
	for (int y = sy; y < sy + 8; y++) {
		for (int x = sx; x < sx + 8; x++) {
			if ((y + x) % 2 == 0) {
				if (board[y][x] != c) cnt++;
			}
			else {
				if (board[y][x] == c) cnt++;
			}
		}
	}
	if (cnt < ans) ans = cnt;
}

int main() {
	cin >> n >> m;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cin >> board[y][x];
		}
	}
	for (int y = 0; y < n - 7;  y++) {
		for (int x = 0; x < m - 7; x++) {
			checkMin('B', y, x);
			checkMin('W', y, x);
		}
	}
	cout << ans;
}