[BF] 1018번 체스판 다시 칠하기

1018번 체스판 다시 칠하기

 

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

 

문제

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

하지만 지민이는 이 보드가 체스판처럼 검정/흰색 패턴이 번갈아가며 색칠해져있지 않기 때문에 고민에 빠졌다. 따라서 지민이는 88크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야 겠다고 생각했다. 당연히 88크기는 아무데서나 골라도 된다.

현재 보드의 색이 어떤지 상태가 주어질 때, 지민이가 8*8크기로 자른 뒤에 다시 칠해야하는 정사각형 개수의 최솟값을 구하는 프로그램을 작성하시오.

체스판은 각 정사각형이 검정 또는 흰색이며, 변을 공유하는 두 개의 사각형이 같은 색이 아닐 때 이다. 따라서 위 정의에 의하면 체스판의 색은 항상 두 가지가 가능한데, 하나는 왼쪽 위 코너가 흰색인 것, 검정색인 것 두가지이다.

 

입력

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

 

출력

첫째 줄에 지민이가 8*8크기로 자른 뒤에 다시 칠해야하는 정사각형 개수의 최솟값을 출력한다.

 

예제 입력

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

 

예제 출력

1

12

 

해결방법

모든 경우를 다 해보는 완전탐색 문제이다

 

시간복잡도를 먼저 생각해봤다

• 최대 배열의 크기는 50*50 이다
• 따라서 8x8 배열은 최대 42*42 개가 나올 수 있다
• 각 8x8 배열은 8*8번 탐색을 한다
• 따라서 112,896 의 시간이 나온다

 

따라서 이 문제는 모든 경우를 전부 탐색할 수 있다

 

여기서 주의할 점은 8x8 배열의 첫번째가 White 로 시작하거나 Black 으로 시작한다는 점이다

따라서 두 가지 경우의 수정 횟수를 모두 구한 다음 최소값을 구해야한다

조금 무식하게 짜긴했지만 잘돌아간다 ㅎㅎ

int solve(int r,int c){
    int changeWhite = 0;
    int changeBlack = 0;
    for(int i=r; i<r+8; i++){
        for(int j=c; j<c+8; j++){
            // 짝수행
            if(i%2==0){
                // 짝수열
                if(j%2==0){
                    if(map[i][j] != 'W') changeWhite++;
                    if(map[i][j] != 'B') changeBlack++;
                }
                // 홀수열
                else{
                    if(map[i][j] != 'B') changeWhite++;
                    if(map[i][j] != 'W') changeBlack++;
                }
            }
            
            // 홀수행
            if(i%2==1){
                // 짝수열
                if(j%2==0){
                    if(map[i][j] != 'B') changeWhite++;
                    if(map[i][j] != 'W') changeBlack++;
                }
                // 홀수열
                else{
                    if(map[i][j] != 'W') changeWhite++;
                    if(map[i][j] != 'B') changeBlack++;
                }
            }
        }
    }
    return min(changeWhite,changeBlack);
}

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 51
#define INF 987654321
using namespace std;

int n,m,ans;
char map[MAX][MAX];

int solve(int r,int c){
    int changeWhite = 0;
    int changeBlack = 0;
    for(int i=r; i<r+8; i++){
        for(int j=c; j<c+8; j++){
            // 짝수행
            if(i%2==0){
                // 짝수열
                if(j%2==0){
                    if(map[i][j] != 'W') changeWhite++;
                    if(map[i][j] != 'B') changeBlack++;
                }
                // 홀수열
                else{
                    if(map[i][j] != 'B') changeWhite++;
                    if(map[i][j] != 'W') changeBlack++;
                }
            }
            
            // 홀수행
            if(i%2==1){
                // 짝수열
                if(j%2==0){
                    if(map[i][j] != 'B') changeWhite++;
                    if(map[i][j] != 'W') changeBlack++;
                }
                // 홀수열
                else{
                    if(map[i][j] != 'W') changeWhite++;
                    if(map[i][j] != 'B') changeBlack++;
                }
            }
        }
    }
    return min(changeWhite,changeBlack);
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
        }
    }
    
    ans = INF;
    for(int i=0; i+8<=n; i++){
        for(int j=0; j+8<=m; j++){
            ans = min(ans,solve(i,j));
        }
    }
    cout << ans << "\n";
    
    return 0;
}