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

문제링크 : https://noj.am/1018

브루트포스 문제로 4중 for문이라는 더러운 코드로 문제를 풀게 되었다.....

체스판의 격자를 다음과 같은 2가지의 임의의 규칙을 정할 수 있다.

1-1. 홀수번째 줄의 홀수 칸이 'W'

1-2. 홀수번째 줄의 짝수 칸이 'B'

1-3. 짝수번째 줄의 짝수 칸이 'W'

1-4. 짝수번째 줄의 짝수 칸이 'B'

or

2-1. 홀수번째 줄의 홀수 칸이 'B'

2-2. 홀수번째 줄의 짝수 칸이 'W'

2-3. 짝수번째 줄의 짝수 칸이'B'

2-4. 짝수번째 줄의 짝수 칸이'W'

위와 같은 조건에 해당이 되지 않는 칸이라면 전부 카운트를 시켜서 값을 누적시키면 다시 칠해야하는 칸이 몇칸인지 구할 수 있다.

하지만 2가지의 case를 모두 비교할 필요 없이 1의 case를 골라서 반전을 시키면 2의 case가 된다.

따라서, 1에서의 cnt를 구해서 64-cnt를 하면 2의 case를 계산할 수 있다.

이러한 법칙에 따라서 문제를 아래와 같이 풀이하면 된다.

// BOJ_1018 체스판 다시 칠하기
#include <iostream>
 
using namespace std;
 
char board[52][52];
 
int min(int a, int b) {
    return a > b ? b : a;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int N, M;
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> board[i][j];
 
    int result = INT32_MAX;
    // x, y 시작 좌표 설정
    for (int x = 1; x <= N - 7; x++) {
        for (int y = 1; y <= M - 7; y++) {
            // 8*8 칸 탐색 및 'B' 카운트
            int cnt = 0;
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    if (i % 2 == 1) { // i가 홀수일 때
                        // j가 홀수이면서 'B'일 때
                        if (j % 2 == 1 && board[x + i][y + j] == 'B')
                            cnt++;
                        // j가 짝수이면서 'W'일 때
                        else if (j % 2 == 0 && board[x + i][y + j] == 'W')
                            cnt++;
                    } else { // i가 짝수일 때
                        // j가 짝수이면서 'B'일 때
                        if (j % 2 == 0 && board[x + i][y + j] == 'B')
                            cnt++;
                        // j가 홀수이면서 'W'일 때
                        else if (j % 2 == 1 && board[x + i][y + j] == 'W')
                            cnt++;
                    }
                }
            }
            // 카운트 누적 값 계산
            cnt = min(cnt, 64 - cnt);
            // 최소값 저장
            result = min(cnt, result);
        }
    }
    cout << result;
 
    return 0;
}