[Brute Force] 백준 1018번 - 체스판 다시 칠하기

 

 

시간 제한 : 2초

시간 제한이 2초 라는 것은 1초에 1억 (10^8)번 계산하는 것의 두배 이므로 2*10^8 이다

하나씩 완전 탐색을 한다고 가정했을 때

     (M-8)*(N-8)*8*8 번 걸린다. 

     M<=50 N<=50 이므로 42 * 42 * 8 * 8 < 2*10^8이므로 충분히 블루트 포스로 문제를 해결할 수 있다. 

 

대각선으로 생각해본다면 (가로index + 세로 index) 가 홀수이냐 짝수이냐에 따라 나뉜다.

 

지민이가 임의의 8x8의 정사각형을 뽑았을 때,

CASE 1) 왼쪽 상단이 Black일 때

(가로index + 세로 index) 가 홀수인 경우 => White

(가로index + 세로 index) 가 짝수인 경우 => Black

 

CASE 2) 왼쪽 상단이 White일 때

(가로index + 세로 index) 가 홀수인 경우 => Black

(가로index + 세로 index) 가 짝수인 경우 => White

 

 

vector로 이차원 배열 만들기

vector<vector<char>> arr;

vector<vector<char>>arr(M, vector<char>(N,'N')); // 이차원 벡터 'N'으로 초기화

//이차원 벡터 탐색 방법

for(int i=0; i<M; i++){
	for(int j=0; j<N; j++){
    	arr[i][j];
    }
}

//해체 방법
for(int i=0; i<arr.size; i++){
	arr[i].clear();
}
arr.clear();

//여러가지 배열의 형태
vector<vector<int>>arr(M, vector<int>(N, 0);

코드

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
#define endl '\n'

int M, N, min_num, cnt1, cnt2;
char input;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> M >> N;
    min_num = 64;
    vector<vector<char> > arr(M, vector<char>(N, 'N'));

    for (int i = 0; i < M; i++)
    {  
        
        for (int j = 0; j < N; j++)
        {
            cin>>input;
            arr[i][j]=input;
        }
    }

    for(int i=0; i<M-7; i++){
        for(int j=0; j<N-7; j++){
            cnt1 = 0; cnt2 = 0;
            //cnt1 - 더한수가 짝수 B, 더한수가 홀수 W
            //cnt2 - 더한수가 짝수 W, 더한수가 홀수 B
            for(int k=i; k<i+8; k++){
                for(int l=j; l<j+8; l++){
                    if((k+l)%2==0){
                        if(arr[k][l]=='B')
                            cnt2++;
                        else
                        {
                            cnt1++;
                        }
                        
                    }
                    else{
                        if(arr[k][l]=='W')
                            cnt2++;
                        else{
                            cnt1++;
                        }
                    }
                }
            }
            int tmp = min(cnt1, cnt2);
            if(tmp<min_num){
                min_num = tmp;
            }
        }
    }
    cout<<min_num<<endl;
}