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

1018번: 체스판 다시 칠하기 (acmicpc.net)

1018번: 체스판 다시 칠하기

올바른 체크판이 될 수 있는 경우는 

10101010
01010101
10101010
01010101
10101010
01010101
10101010
01010101

01010101
10101010
01010101
10101010
01010101
10101010
01010101
10101010

(흰색이 0, 흑색이 1)

 

이 두 가지밖에 없기 때문에, 처음에는 입력받은 보드를 순회하면서 8*8 체크보드를 만들 수 있는 모든 경우에 대해, top-left 칸이 어떤 색인지에 따라서 정답보드 1(top-left가 백),정답보드 2(top-left가 흑)와 비교하여 최소값을 업데이트했다.

 

그런데 틀려서, 예시 답안을 보면서 가만 다시 생각해 보니

 

1. 첫 번째 칸을 지금 이대로 놔두고 색칠하는 경우

2. 첫 번째 칸을 지금과 다르게 색칠하는 경우

 

이 두 가지 경우를 모두 고려해야 했다. 즉 top-left 칸의 색을 구별할 필요가 없이, 정답보드 1, 정답보드 2와 모두 비교하는 문제였다.

 

정답코드 첨부하고 마친다.

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

int minPaint = 100;
vector<vector<int>> answerBoard_1 = {
    {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}};
vector<vector<int>> answerBoard_2 = {
    {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}};

void checkBoard(int initRow, int initCol, vector<vector<int>> &inputBoard, vector<vector<int>> &answerBoard)
{
    int paintCnt = 0;
    /* cout << "check will be ended at " << initRow + 8 << " " << initCol + 8 << endl; */
    for (int i = initRow; i < initRow + 8; i++)
    {
        for (int j = initCol; j < initCol + 8; j++)
        {
            if (inputBoard[i][j] != answerBoard[i - initRow][j - initCol])
            {
                paintCnt++;
            }
        }
    }

    minPaint = min(minPaint, paintCnt);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int M;
    int N;

    cin >> M;
    cin >> N;
    vector<vector<int>> inputBoard(M, vector<int>(N));

    // white = 0, black = 1
    string boardInput;
    for (int i = 0; i < M; i++)
    {
        cin >> boardInput;
        for (int j = 0; j < N; j++)
        {
            if (boardInput.at(j) == 'W')
            {
                inputBoard[i][j] = 0;
            }
            else if (boardInput.at(j) == 'B')
            {
                inputBoard[i][j] = 1;
            }
        }
    }

    for (int i = 0; i < M - 7; i++)
    {
        for (int j = 0; j < N - 7; j++)
        {
            checkBoard(i, j, inputBoard, answerBoard_1);
            checkBoard(i, j, inputBoard, answerBoard_2);
        }
    }

    cout << minPaint;
}