백준 1018 : 체스판 다시 칠하기

문제 링크입니다 https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

두 가지 경우의 8 x 8 체스판을 만들어 놓고 입력받은 체스판에서 8 x 8로 탐색할 수 있는 모든 경우를 탐색하며 만들어놓은 체스판과 비교하며 다른 칸의 개수를 세어주어 최솟값을 찾는 문제였습니다.

 

 

[소스코드]

 

// [Brute Force] 백준(1018) : 체스판 다시 칠하기
 
#include<cstdio>
const int MAX = 50 + 10;
 
int n, m, map[MAX][MAX], result1[MAX][MAX], result2[MAX][MAX];
 
// 만들어놓은 체스판과 다른 칸이 몇 개인지 비교해주는 함수
int getResult(int y, int x) {
    int cnt1 = 0, cnt2 = 0;
    for (int i = y; i < y + 8; i++) {
        for (int j = x; j < x + 8; j++) {
            if (map[i][j] != result1[i - y][j - x]) cnt1++;
            if (map[i][j] != result2[i - y][j - x]) cnt2++;
        }
    }
    return cnt1 < cnt2 ? cnt1 : cnt2;
}
 
void solve(void) {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char x;
            scanf(" %c", &x);
            // 1과 -1로 나누어 입력을 받습니다
            if (x == 'B') map[i][j] = 1;
            else map[i][j] = -1;
        }
    }
 
    int ret = 987987987;
    int value = 1;
    
    // 8x8 체스판을 두 가지 경우로 나누어 만듭니다(배열의 원소는 1과 -1로)
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            result1[i][j] = value, result2[i][j] = -value;
            value = -value;
        }
        value = -value;
    }
    // 8x8로 검사할 수 있는 모든 경우를 탐색합니다
    for (int i = 0; i <= n - 8; i++) {
        for (int j = 0; j <= m - 8; j++) {
            int temp = getResult(i, j);
            if (ret > temp) ret = temp;
        }
    }
    printf("%d", ret);
}
 
int main(void) {
    solve();
    return 0;
}