백준 #1018 체스판 다시 칠하기

블랙과 화이트가 일정규칙이 아닌 체스 보드가 있습니다.  체스판은 블랙과 화이트가 교차되어 나열되어있고, 세로방향도 마찬가지입니다.  총 8칸, 8열이 있어서, 32칸의 블랙칸과 32칸의 화이트칸이 서로 같은색끼리는 인접하지 않고 있습니다.  이번 문제는 블랙과 화이트가 엉망인 체스 보드에 칠을 최소한으로 칠하고자 할 때, 칠한 횟수를 구하는 것입니다.

 

체스판 다시 칠하기

더구나 이 체스 보드는 8x8 보다 클 수도 있어서, 칠하는 횟수를 적게할 수 있도록 8x8 구역도 정해야 합니다.

 

백준 사이트의 문제는 아래의 링크에 있습니다.

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

1018번: 체스판 다시 칠하기

 

가장 무식한 방법으로는, 8x8판의 모든 색을 검사하여 최소비용의 칠 횟수를 구하는 것입니다.  8x8인 판이라면 총 64번의 검사비용이 필요하겠지만, 15x15 인 체스 보드라면 총 4,096번의 검사 비용이 듭니다.  문제의 범위대로 50x50 이라면, 78,400번의 검사 비용이 듭니다.

 

사실 뭐 이정도면, 단순 무식하게 처리해도 됩니다.  이 문제는 시간초과로 질문 올리신 분도 없고 맞은 분들은 대부분 0ms 이내에서 처리했습니다.  문제의 유형에서 봐도 브루트포스 방식이 나와있습니다.  한쪽 방향이면 어떻게든 효율좋게 짜볼텐데요.

 

아래는 제가 작성한 소스입니다.  참고용으로만 봐주세요.

//------------------------------------------------------------------------------
//  baekjoon #1018 - Paint Chess Board Again.
//    - by Aubrey Choi
//    - created at 2019-06-13
//------------------------------------------------------------------------------
#include <stdio.h>

int count(char board[][50], int x, int y)
{
  int miss = 0;
  for(int i = y; i < y+8; i++)
  {
    for(int j = x; j < x+8; j++)
    {
      if(board[i][j] ^ ((i+j)%2)) miss++;
    }
  }
  return miss >= 32 ? 64-miss : miss;
}

int main()
{
  int m, n;
  char board[50][50];
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; i++)
  {
    char str[100];
    scanf("%s", str);
    for(int j = 0; j < m; j++)
    {
      board[i][j] = (str[j] == 'B');
    }
  }
  int min = 32;
  for(int i = 0; i <= n - 8; i++)
  {
    for(int j = 0; j <= m - 8; j++)
    {
      int s = count(board, j, i);
      if(min > s) min = s;
    }
  }
  printf("%d\n", min);
  return 0;
}