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

문제 링크

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

 

 

전체 보드를 8*8크기의 보드로 분할했을 때 분할된 보드가 체스판이 되기 위해 수정해야 하는 정사각형의 최솟값을 출력해야 합니다.

8*8 보드의 첫 칸의 좌표를 (0, 0)이라 했을 때, 좌표 (i, j)에서 i+j가 홀수인 칸들이 모두 같은 색이고, 짝수인 칸들이 모두 같은 색이어야 합니다.

(0, 0) 정사각형이 흰색일 때와 검은색일 때를 모두 고려해서 수정해야 하는 정사각형의 수를 구하면 됩니다.

 

 

정답 코드

#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f
 
int n, m;
char p[100][100];
int foo(int x, int y) {
    if (x + 7 >= n || y +7 >= m) return INF;
    int a = 0, b = 0;
 
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            int nx = x + i, ny = y + j;
            
            if ((i + j) % 2 == 0)
                if (p[nx][ny] != 'W') a++;
                else b++;
            else if ((i + j) % 2 != 0)
                if (p[nx][ny] != 'B') a++;
                else b++;
        }
    }
    return a < b ? a : b;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    int ans = INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int val = foo(i, j);
            ans = ans < val ? ans : val;
        }
    }
    cout << ans;
}