백준 1018번 문제 - 체스판 다시 칠하기

---

문제 링크: https://www.acmicpc.net/problem/1018

체스판 다시 칠하기 문제는 8x8 크기의 체스판으로 만들 때 체스판의 경우의 수가 좌상단 첫번째 칸이 흰색인 경우와 검은색인 경우 두가지 밖에 없다는 점을 읽었다면 쉽게 풀 수 있는 문제이다.

NxM의 보드판이 주어졌을 때 8x8의 체스판을 구하기 위해 정할 수 있는 시작점은 (0,0)부터 (N-8,M-8)까지 가능하다.

가능한 각 시작점을 기준으로 8x8의 가능한 체스판 2개에 대해 불일치한 수를 구해 최소값을 구함으로서 해답을 구할 수 있다.

#include<iostream>
using namespace std;
#define MAXSIZE 51
#define CHESSSIZE 8
int N,M,result=64;//8x8이므로 아무리 색을 다시칠해도 64의 결과가 나올 수 없음
char arr[MAXSIZE][MAXSIZE];

int check(int n,int m){ //8x8에서 인접한 위치와 충돌이 일어나는 수
    int result1=0, result2=0;
    for(int i=0;i<CHESSSIZE;i++){
        for(int j=0;j<CHESSSIZE;j++){
            if(i%2==j%2){//0,0 || 1,1
                if(arr[n+i][m+j]!='W') result1++;
                if(arr[n+i][m+j]!='B') result2++;
            }else{//0,1 || 1,0
                if(arr[n+i][m+j]!='B') result1++;
                if(arr[n+i][m+j]!='W') result2++;
            }
        }
    }
    return (result1<result2)?result1:result2;
}

int main(){
    scanf("%d %d",&N,&M);
    for(int i=0;i<N;i++) scanf("%s",&arr[i]);
    
    //풀이 1: 가장 간단한 방법, N-8, M-8의 경우의 수를 전부 조사하여 최소값 구하기
    for(int i=0;i<=N-8;i++){//시작점 세팅
        for(int j=0;j<=M-8;j++){
            int temp = check(i,j);
            result = (result>temp)?temp:result;
        }
    }
    printf("%d\n",result);
}