[ 백준 1018 ] 체스판 다시 칠하기 (C++)

백준의 체스판 다시 칠하기(1018) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 주어진 맵에서 8x8 크기만큼 떼어냈을 때, 다시 칠해야 하는 정사각형의 수의 최솟값을 구하는 문제이다.

   체스판은 가장 왼쪽 위가 흰색인 판이있고, 검정색인 판이 있다.

   즉, 우리는 이 문제를 해결하기위해서 떼어낼 수 있는 모든 8x8크기의 판에서, 가장 왼쪽 위가 흰색인 판일때의 최솟값과

   가장 왼쪽위가 검은색 판일때의 최솟값을 비교해서 더 작은 값을 정답으로 갱신해 주면석 반복하면 된다.

2) 그렇다면 맵에서 8 x 8을 어떻게 떼어내올까?? 사실상 for문을 통해서 모든 정점을 통해서 8x8 판을 떼어내오면 된다.

   여기서 정점이라는 것은 8 x 8 크기로 나눴을 때 가장 왼쪽 위 좌표를 의미한다.

   물론, 해당 정점에서 가로 세로로 8칸씩 더했을 때, 맵의 범위를 벗어나버리는 정점이라면, 그 정점에 대해서는 진행을

   하지 않아도 된다.

   우리가 해야할 것을 깔끔하게 정리해보자.

   1. 모든 정점을 돌면서, 해당 정점이 8x8 크기의 판을 만들 수 있는 정점인지 ?

   2. 가장 왼쪽 위의 좌표를 흰색으로 두었을 때 다시 칠해야 할 정사각형의 갯수가 몇개인지?

   3. 가장 왼쪽 위의 좌표를 검은색으로 두었을 때 다시 칠해야 할 정사각형의 갯수가 몇개인지?

   위의 3가지를 코드로 나타내면 아래와 같다.

for (int i = 0; i < N; i++)
    {
        if (i + 8 > N) break;
        for (int j = 0; j < M; j++)
        {
            if (j + 8 > M) break;
 
            White_First_Min = Make_White_First(i, j);
            Black_First_Min = Make_Black_First(i, j);
            Total_Min = Min(Total_Min, Min(White_First_Min, Black_First_Min));
        }
    }

3) 그렇다면 가장 왼쪽 위의 좌표가 흰색일 때, 검은색일 때, 다시 칠해야 할 정사각형의 갯수를 Count하는 방법을 알아보자.

  

   이렇게 2개의 판이 있다. 먼저 왼쪽 위가 흰색인 판부터 보자.

   보면, 0을 포함한 짝수행에서는 짝수 열일 때 흰색. 홀수행에서는 홀수 열일 때 흰색이라는 것을 찾을 수 있다.

   (0, 0), (2, 0), (2, 2) = 흰색.

   (1, 1), (3, 5), (7, 7) = 흰색

   반면 검은색은, 0을 포함한 짝수 행에서 홀수 열일 때 검은색. 홀수 행에서는 짝수 열일때 검은색이다.

   위의 내용을 코드로 구현하면 아래와 같다.

for (int i = x; i < x + 8; i++)
    {
        for (int j = y; j < y + 8; j++)
        {
            if (i == x || i == x + 2 || i == x + 4 || i == x + 6)
            {
                if (j == y || j == y + 2 || j == y + 4 || j == y + 6)
                {
                    if (MAP[i][j] != 'W') Cnt++;
                }
                else
                {
                    if (MAP[i][j] != 'B') Cnt++;
                }
            }
            else
            {
                if (j == y || j == y + 2 || j == y + 4 || j == y + 6)
                {
                    if (MAP[i][j] != 'B') Cnt++;
                }
                else
                {
                    if (MAP[i][j] != 'W') Cnt++;
                }
            }
        }
    }

   위의 코드는 왼쪽 위가 흰색일 때 체스판을 다시 칠해야 하는 갯수를 Count하는 코드이다.

  

   위의 코드를 제대로 이해했다면, 왼쪽 위가 검은색일 때 체스판을 다시 칠해야 하는 경우도 쉽게 해결할 수 있을 것이다.

   위의 부분을 모두 구현했다면, 이 후에 해야할 일은 뭐가 있을까??

   1. 왼쪽 위가 흰색일 때 최소인지 검은색일 때 최소인지 비교해서 최소값 찾기

   2. 그 최소값과 현재 전체 최소값을 비교해서 갱신해주기 !

  

[ 소스코드 ]

#include<iostream>
 
#define MAX 50
using namespace std;
 
int M, N;
char MAP[MAX][MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
int Estimate_Num(int a)
{
    if (a % 2 == 0) return 0;
    else return 1;
}
 
int Make_White_First(int x, int y)
{
    //x가 0일수도 잇고 1일수도 잇어
    //y도 0일수도 잇고 1일수도 잇어
    int Cnt = 0;
 
    for (int i = x; i < x + 8; i++)
    {
        for (int j = y; j < y + 8; j++)
        {
            if (i == x || i == x + 2 || i == x + 4 || i == x + 6)
            {
                if (j == y || j == y + 2 || j == y + 4 || j == y + 6)
                {
                    if (MAP[i][j] != 'W') Cnt++;
                }
                else
                {
                    if (MAP[i][j] != 'B') Cnt++;
                }
            }
            else
            {
                if (j == y || j == y + 2 || j == y + 4 || j == y + 6)
                {
                    if (MAP[i][j] != 'B') Cnt++;
                }
                else
                {
                    if (MAP[i][j] != 'W') Cnt++;
                }
            }
        }
    }
    return Cnt;
}
 
int Make_Black_First(int x, int y)
{
    int Cnt = 0;
 
    for (int i = x; i < x + 8; i++)
    {
        for (int j = y; j < y + 8; j++)
        {
            if (i == x || i == x + 2 || i == x + 4 || i == x + 6)
            {
                if (j == y || j == y + 2 || j == y + 4 || j == y + 6)
                {
                    if (MAP[i][j] != 'B') Cnt++;
                }
                else
                {
                    if (MAP[i][j] != 'W') Cnt++;
                }
            }
            else
            {
                if (j == y || j == y + 2 || j == y + 4 || j == y + 6)
                {
                    if (MAP[i][j] != 'W') Cnt++;
                }
                else
                {
                    if (MAP[i][j] != 'B') Cnt++;
                }
            }
        }
    }
    return Cnt;
}
 
void Make_Chess()
{
    int White_First_Min;
    int Black_First_Min;
    int Total_Min = 9999;
 
    for (int i = 0; i < N; i++)
    {
        if (i + 8 > N) break;
        for (int j = 0; j < M; j++)
        {
            if (j + 8 > M) break;
 
            White_First_Min = Make_White_First(i, j);
            Black_First_Min = Make_Black_First(i, j);
            Total_Min = Min(Total_Min, Min(White_First_Min, Black_First_Min));
        }
    }
    cout << Total_Min << endl;
}
 
void Solution()
{
    Make_Chess();
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}