[BOJ/1018/C++] 체스판 다시칠하기

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

문제

• 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

• 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

조건

• 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

• 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

SOL

뭔가 어려운듯하면서, 막상 풀어보면 쉬운 문제이다. 하지만, 몇가지 함정을 파놓았는데 체스판이 2가지 종류만 있다는 점을 보고 두 개의 체스판을 각각 저장한 뒤, 하나씩 다 비교해보자는 BruteForce로 접근하면 괜찮지만,
혹시 "B"로 시작한다면, 당연히 B로 시작하는 Chessbaord가 유리하지 않을까라고 생각하면서 B로 시작하는 체스보드로 고정시키면 안된다!

아래와 같은 반례가 있을 수 있다.

BBW ==> BWB
BWB ==> WBW
WBW ==> BWB

위 보드는 B로 시작하지만, 무려 8개를 바꿔야 B로 시작하는 Chess board가 된다. 반대로 W로 시작하는 W보드로 만들면, 맨앞 B 하나만 바꾸면 되므로 , 반례가 존재하게 된다.

그러므로, B,W로 시작하는 체스판의 경우를 모두 봐야 결국은 알게되므로 전부 다 보아야한다. 탐색하는 로직은 if문으로 짜도되지만, 간편하게 B,W Board를 직접 저장해서 비교하는게 더 간편하고 빠르다. 어차피 케이스는 정해져 있기 때문이다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

string board[51];

char black_chessboard[8][8] = {
    {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
    {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
    {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
    {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
    {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
    {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
    {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
    {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
};
char white_chessboard[8][8] = {
    {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
    {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
    {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
    {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
    {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
    {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
    {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
    {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
};

int make_chessboard(int start_y, int start_x)
{
  int b_cnt = 0, w_cnt = 0;

  for (int y = 0; y < 8; y++)
  {
    for (int x = 0; x < 8; x++)
    {
      if (board[y + start_y][x + start_x] != black_chessboard[y][x])
        b_cnt++;
      if (board[y + start_y][x + start_x] != white_chessboard[y][x])
        w_cnt++;
    }
  }
  return min(b_cnt, w_cnt);
}

int main()
{
  int N, M;
  cin >> N >> M;
  int ans = INT_MAX;
  string tmp;
  for (int i = 0; i < N; i++)
  {
    cin >> tmp;
    board[i] = tmp;
  }
  for (int y = 0; y <= N - 8; y++)
  {
    for (int x = 0; x <= M - 8; x++)
    {
      ans = min(ans, make_chessboard(y, x));
    }
  }
  cout << ans << '\n';
  return 0;
}