[백준] 1018 체스판 다시 칠하기 brute force

문제 :

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

1018번: 체스판 다시 칠하기

 

풀이 :

인풋으로 주어진 배열과 주어진 8x8 배열과 cnn 모델처럼 필터링하듯이 비교하는 문제였다. 따라서 브루트포스로 비교할 체스판의 범위를 먼저 정하고, 블랙으로 시작하는 체스판 or 흰색으로 시작하는 체스판 두가지 경우의 수와 대조하여 min 값을 찾아낸다.

 

우선 for문이 많다는 점에 시간 초과가 날까 걱정했지만 

체스판의 크기 M x N 와 (50 x 50)과 만든 체스판의 크기 8 x 8을 두번 비교하므로 총

50 x 50 x 8 x 8 x 2 < 10^8 이므로 시간 초과가 나지는 않았다.

 

c++ 코드 : 

//
//  1018_reDrawChess.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/09/10.
//

#include <stdio.h>
#include <iostream>

using namespace std;
int col, row;
string arr[51];

int min_val = 1000000;
string WB[8] = {
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW"
};
string BW[8] = {
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB"
};

int WB_cnt(int x, int y)
{
    int cnt = 0;
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            if(arr[x+i][y+j] != WB[i][j])
                cnt++;
        }

    }
    return cnt;
}

int BW_cnt(int x, int y)
{
    int cnt = 0;
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            if(arr[x+i][y+j] != BW[i][j])
                cnt++;
        }

    }
    return cnt;
}
int main() {
    cin >> col >> row;
    for(int i = 0; i < col; i++)
        cin >> arr[i];
    
    for(int i = 0; i + 8 <= col; i++)
    {
        for(int j = 0; j + 8 <= row; j++)
        {
            int tmp;
            tmp = min(WB_cnt(i,j),BW_cnt(i,j));
            if(tmp < min_val) {
                min_val = tmp;
            }
        }
    }
    cout << min_val << '\n';
    return 0;
}