[BOJ] 1018

체스판 다시 칠하기

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

분류

• Silver 5

• 브루트포스 알고리즘

해법

M * N 크기의 체스판을
왼쪽 위의 지점이 (0, 0) -> (0, 1) -> (0, 2) -> … -> (1, 0) -> (1, 1) -> … -> (M - 8, N - 8)
이 되는 8 * 8 크기의 체스판으로 나눕니다.

위에서 나눈 각 체스판들을
흰, 검, 흰, 검 으로 시작하는 체스판으로 칠하는 방식과
검, 흰, 검, 흰 으로 시작하는 체스판으로 칠하는 방식 중
어느쪽이 더 적게 색칠할 수 있는지 비교합니다.

정답 코드

#include <iostream>
using namespace std;

// check how many blocks have to be painted newly
int NewPaint(const char arr[][50], const int &i, const int &j)
{
    // start with white
    int cntW = 0;
    char color = 'B';
    for (int idx1 = i; idx1 < i + 8; idx1++)
    {
        color = (color == 'B') ? 'W' : 'B'; // next block color should be equal with color
        for (int idx2 = j; idx2 < j + 8; idx2++)
        {
            cntW = (arr[idx1][idx2] == color) ? cntW : cntW + 1; // if arr[idx1][idx2] is not equal with color, we should re-paint this block
            color = (color == 'B') ? 'W' : 'B'; // next block color should be equal with color
        }
    }

    // start with black
    int cntB = 0;
    color = 'W';
    for (int idx1 = i; idx1 < i + 8; idx1++)
    {
        color = (color == 'B') ? 'W' : 'B'; // next block color should be equal with color
        for (int idx2 = j; idx2 < j + 8; idx2++)
        {
            cntB = (arr[idx1][idx2] == color) ? cntB : cntB + 1; // if arr[idx1][idx2] is not equal with color, we should re-paint this block
            color = (color == 'B') ? 'W' : 'B'; // next block color should be equal with color
        }
    }

    return (cntW < cntB) ? cntW : cntB;
}

// check all cases
void ChessSelect(const char arr[][50], const int &n, const int &m)
{
    int min = 2501; // min can't be bigger than 2500
    for (int i = 0; i <= n - 8; i++)
        for (int j = 0; j <= m - 8; j++)
        {
            int k = NewPaint(arr, i, j);
            min = (k < min) ? k : min;
        }

    cout << min;
}

int main(void)
{
    char arr[50][50];
    int n, m;
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf(" %d", &arr[i][j]);

    ChessSelect(arr, n, m);
    
    return 0;
}