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

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

문제를 해결하기 위해 접근한 방법은 다음과 같다.

1. 왼쪽 상단이 W로 시작할 때, W와 B가 와야할 자리에 다른 문자가 오면 1로 표시를 한다.

2. 8*8만큼의 체스판에서 W로 시작할 때 바꿔야할 문자의 개수를 구한다.

3. 8*8만큼의 체스판에서 B로 시작할 때 바꿔야할 문자의 개수를 구한 뒤에 (64에서 W로 시작할 때 바꿔야할 문자 개수를 빼주면 된다)

   W로 시작할 때 바꿔야할 문자 개수와의 비교 후, 최소값을 구한다.

4.왼쪽 상단의 좌표를 변경하면서 바꿔야할 문자 개수의 최소값을 업데이트 해준다.

vec라는 2차원 배열을 만든 후에 W로 시작할 때 바꿔야할 문자를 1로 세팅을 해주면

0이 있는 좌표들은 B로 시작할 때 바꿔야할 문자의 자리라는 것을 의미한다.

그렇기 때문에 W로 시작할때 바꿔야할 문자의 개수를 구한다면 B로 시작할 때 바꿔야할 문자의 개수도 바로 알 수 있다.

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
 
int N,M;
vector<vector<char>> map;
vector<vector<int>> vec;
 
int main(){
    
    cin>>N>>M;
    map=vector<vector<char>> (N,vector<char>(M,0));
    vec=vector<vector<int>> (N,vector<int>(M,0));
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>map[i][j];
 
            //'W'로 시작할 때 각 자리에 W,B가 오지 않는 경우
            if((i+j)%2==0 && map[i][j]!='W')    vec[i][j]++;
            if((i+j)%2==1 && map[i][j]!='B')    vec[i][j]++;
        }
    }
 
    int ans=N*M;
    for(int i=0;i+7<N;i++){
        for(int j=0;j+7<M;j++){
            
            int cnt=0;
            for(int y=0;y<8;y++){
                for(int x=0;x<8;x++){
                    cnt+=vec[i+y][j+x];
                }
            }
            
            //'W'로 시작할 때 바꿔야할 문자 개수(cnt)와 'B'로 시할 때 바꿔야할 문자 개수(64-cnt)
            cnt=min(cnt,64-cnt); 
            ans=min(ans,cnt);
        }
    }
    cout<<ans<<endl;
    return 0;
}