[BOJ] 백준 1018 체스판 다시 칠하기

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

 Input 

10 13

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

WWWWWWWWWWBWB

WWWWWWWWWWBWB

 

 Output 

12

 

① N * M 크기의 board를 8 × 8로 잘나 낼 수 있는 모든 경우의 수 구하기

ex) 9 × 9 크기에서는 4가지 경우가 존재

② 8 × 8크기로 잘나낸 board에서 색을 바꾸어야할사각형의 개수를 합니다.

    - 흰색 / 검은색으로 시작하는 경우 중 색이 바뀌는 개수가 더 작은 것을 구합니다.

③ 전체 Case 중 ②에서 구한 값 중 최소값을 구합니다.

    각 Case마다 기존 최솟값 개수와 비교하며 갱신해 줍니다.

---

#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAX 9999;
 
int N, M;
char map[60][60];
char board[8][8];
 
void makeBoard(int x, int y){
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            board[i][j] = map[x + i][y + j];
        }
    }
}
 
int solve(){
    int countBlack = 0, countWhite = 0;
 
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            // 왼쪽상단이 검은색으로 시작하는 경우
            if ((i + j) % 2 == 0 && board[i][j] == 'W') ++countWhite;
            if ((i + j) % 2 == 1 && board[i][j] == 'B') ++countWhite;
            
            // 왼쪽 상단이 흰색으로 시작하는 경우
            if ((i + j) % 2 == 0 && board[i][j] == 'B') ++countBlack;
            if ((i + j) % 2 == 1 && board[i][j] == 'W') ++countBlack;
        }
    }
    
    // 두 경우 최소값을 반환
    return min(countBlack, countWhite);
}
 
int main(void){
    int result = MAX;
    cin >> N >> M;
 
    memset(map, 0, sizeof(map));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> map[i][j];
        }
    }
 
    for (int x = 0; x <= N - 8; ++x) {
        for (int y = 0; y <= M - 8; ++y) {
            // 8x8 크기로 잘라내기
            makeBoard(x, y); 
            // 기존 최소값과 비교해서 더 작은값으로 갱신 시도
            result = min(result, solve());
        }
    }
 
    cout << result;
    return 0;
}