브루트포스 - 백준 1018번 체스판 다시 칠하기

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

IDEA

50 * 50 짜리를 8 * 8로 쪼개 완전탐색을 진행해도 십만번이 조금 넘기때문에 주어진 시간 안에 돌아갈 수 있다고 판단했다. 

 

• 체스판의 구성은 왼쪽 위가 W냐 , B냐에 따라서 달라진다.
  그래서 나는 왼쪽 위가 W면 WHITE 배열 , B면 BLACK배열이라고 두었다.
  WHTE 배열 - 홀수번째 행 & 홀수번째 열 : W , 홀수번째 행 & 짝수번째 열 : B
                    짝수번째 행 & 홀수번째 열 : B , 짝수번째 행 & 짝수번째 열 : W 이라는 규칙이 있다.
  BLACK배열은 정반대이다. 
  맨 처음 보드판을 입력받을 때, 행과 열에 따라서 잘못된 색깔이 온 경우 해당 체스판의 좌표를 1로 채워줬다. 

 

•  M x N 체스판을 오른쪽으로 , 아래로 이동하며 8개씩 잘라가며 보았다.
  64개 안에 BLACK배열의 1이 몇 개 있는지 , WHITE 배열이 몇 개 있는지 COUNT한 후, 최솟값을 업데이트 했다.

CODE 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

char arr[51][51];
int black[51][51];
int white[51][51];

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            //black일 때 -> 홀수행, 홀수열 B 홀수행 짝수열 W 짝수행 홀수열 w , 짝수행 짝수열 B
            if (i % 2 == 1 && j % 2 == 1) arr[i][j] == 'W' ? black[i][j] = 1 : white[i][j] = 1;
            else if (i % 2 == 1 && j % 2 == 0) arr[i][j] == 'B' ? black[i][j] = 1 : white[i][j] = 1;
            else if (i % 2 == 0 && j % 2 == 1) arr[i][j] == 'B' ? black[i][j] = 1 : white[i][j] = 1;
            else arr[i][j] == 'W' ? black[i][j] = 1 : white[i][j] = 1;
        }
    }
  
    int bcnt = 0, wcnt = 0, min_cnt = 100;
    // 큰 틀 
    for (int i = 1; i <= m - 7; i++) {
        for (int j = 1; j <= n - 7; j++) {
        // 그 안에서 뽑기 시작점 i,j
            bcnt = 0, wcnt = 0;
            for (int x = i; x < i + 8; x++) {
                for (int y = j; y < j + 8; y++) {
                    if (black[x][y]) bcnt++;
                    if (white[x][y]) wcnt++;
                }
            }
            min_cnt = min({ min_cnt , bcnt , wcnt });
        }
    }
    printf("%d", min_cnt);
}