[백준] 1018번. 체스판 다시 칠하기

[문제]

 

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

[풀이]

 

하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우 서로 완전 반대의 상태가 된다.

따라서 하나의 상태만 구해놓고 반대로 생각하면 된다.

 

검은색은 1, 흰색은 0으로 구분하여 int형이 아닌 bool형 배열을 사용했다.

먼저 맨 왼쪽 위 칸이 검은색인 경우를 구해서 b라는 배열에 저장했다.

 

그리고 반복문을 통해 모든 좌표에 대해서

(x,y)가 맨 왼쪽 위 칸이 되어 8*8 크기의 배열로 현재 주어진 입력에서 검은색과 흰색에 대해 각각 바꿔야하는 칸의 갯수를 확인했다. 

 

이러한 방법으로 (0,0)부터 (N-8,M-8)까지 확인하면서 다시 칠해야 하는 정사각형의 최소 개수를 구할 수 있었다.

모든 좌표에 대해서 확인해줘야 하므로 시간초과를 걱정했지만 

배열의 최대 크기가 50*50 이므로 시간초과는 발생하지 않는다.

 

[코드]

 

시간 : 0ms

 

#include <iostream>
#include <algorithm>
#include <queue>

#define MAX 51

using namespace std;

struct pos{
    int x,y;
};

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int N,M;
bool visited[MAX][MAX]={0,};
bool map[MAX][MAX]={0,};
bool b[MAX][MAX]={0,};

void black()
{
    queue <pos> q;
    b[0][0]=true;
    q.push({0,0});
    visited[0][0]=true;
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx<0||ny<0||nx>=N||ny>=M||visited[nx][ny])   continue;
            if(b[x][y]==false) b[nx][ny] = true;
            q.push({nx,ny});
            visited[nx][ny]=true;
        }
    }
}


int solve(int x,int y)
{
    int b_cnt=0;
    int w_cnt=0;
    
    for(int i=x;i<x+8;i++){
        for(int j=y;j<y+8;j++){
            if(map[i][j] != b[i][j])    b_cnt++;
        }
    }
    for(int i=x;i<x+8;i++){
        for(int j=y;j<y+8;j++){
            if(map[i][j] == b[i][j])    w_cnt++;
        }
    }
    return min(b_cnt,w_cnt);
}
int main(void)
{
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            char ch;
            cin >> ch;
            if(ch=='B')    map[i][j]=true;
        }
    }
    
    int ans = MAX*MAX;
    black();
    
    for(int i=0;i<=N-8;i++){
        for(int j=0;j<=M-8;j++){
            ans = min(ans,solve(i,j));
        }
    }
    cout << ans;
    return 0;
}