1018)체스판 다시 칠하기

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

문제를 이해해보자.

우선 처음에 주어지는 나무판은 체스판처럼 체크 무늬가 교차해서 나타나지 않는다.

주어진 나무판에서 아무데서나 8x8 모양을 잘라낸 다음

잘라낸 나무판이 체스판 모양이 될 수 있도록 체크 무늬를 다시 칠할 것이다.

이때 다시 칠하는 횟수가 최소가 되는 값을 찾아야 한다.

예를 들어보자.

나무판이 위처럼 엉망으로 주어질 수 있다.

여기서 8x8 이되게 나무판을 자르는 경우는 아래와 같다.

 

즉 빨강 사각형을 옮겨 가며 다시 칠해야 할 색의 수를 세어 그중에서 최소인 것을 찾으면 된다.

여기서 하나 더 고려할 것이 있다.

체스 무늬는 왼쪽 위 모서리에서 흰색으로 시작하는 패턴이 있고 검은색으로 시작하는 패턴이 있다.

왼쪽 위 모서리가 흰색으로 시작하는 경우 체크 패턴은 왼쪽 그림과 같이 나타나야 하고

검은색으로 시작하는 경우 체크 패턴은 오른쪽 그림과 나타나야 한다.

흰색을 0이라 하고 검은색을 1이라 하자.

이중 반복문으로 i,j값을 차례로 증가시키며 체크 패턴을 결정할 때 체크 무늬를 만들기 위한 식은 (i+j)%2 이다.

시작이 흰색 인경우 올바른 체크 무늬를 만드는 식은 0+(i+j)%2이고

시작이 검은색인 경우 올바른 체크 무늬를 만드는 식은 1+(i+j)%2이다.

위처럼 빨강색 상자 안에서 한 칸씩 올바른 체크 무늬 패턴인지 비교한다.

올바른 체크 무늬가 아닌 경우 색을 덧칠해야 하므로 카운팅한다.

올바른 체크 무늬는 두 경우가 있으니 다른 체크 무늬와도 비교해 작은 값이 나온 것을 선택한다.

#include<stdio.h>
 
#define CHESS_ROW 8
#define CHESS_COLUMN 8
#define BLACK_NUM 32
#define WHITE_NUM 32
#define MAX 2500
#define BLACK 1
#define WHITE 0
 
int repaintCount(char chessBoard[50][51], int rowStart, int columnStart) {
    int white = 0, black = 0;
    int repaint = 0;
    int minRepaint;
    int startColor;
    int correctColor;
 
    startColor = (rowStart + columnStart) % 2;
    for (int i = rowStart; i < rowStart + CHESS_ROW; i++) {
        for (int j = columnStart; j < columnStart + CHESS_COLUMN; j++) {
 
            correctColor = (startColor + i + j) % 2;
            if (chessBoard[i][j] == 'B') {
                if (correctColor != BLACK) {
                    repaint++;
                }
            }
            else {
                if (correctColor != WHITE) {
                    repaint++;
                }
            }
        }
    }
    minRepaint = repaint;
    repaint = 0;
 
    startColor = (rowStart + columnStart) % 2 + 1;
    for (int i = rowStart; i < rowStart + CHESS_ROW; i++) {
        for (int j = columnStart; j < columnStart + CHESS_COLUMN; j++) {
 
            correctColor = (startColor + i + j) % 2;
            if (chessBoard[i][j] == 'B') {
                if (correctColor != BLACK) {
                    repaint++;
                }
            }
            else {
                if (correctColor != WHITE) {
                    repaint++;
                }
            }
        }
    }
 
    minRepaint = (minRepaint > repaint) ? repaint : minRepaint;
    return minRepaint;
}
 
int main() {
    int M, N;
    int black = 0, white = 0;
    int tempRepaint;
    int minRepaint = MAX;
    char S[50][51];
 
    scanf("%d %d", &M, &N);
    for (int i = 0; i < M; i++) {
        scanf("%s", S[i]);
    }
 
    for (int i = 0; i < M - CHESS_ROW + 1; i++) {
        for (int j = 0; j < N - CHESS_COLUMN + 1; j++) {
            tempRepaint = repaintCount(S, i, j);
            minRepaint = (minRepaint > tempRepaint) ? tempRepaint : minRepaint;
        }
    }
 
    printf("%d\n", minRepaint);
    return 0;
}