백준 25682 : 체스판 다시 칠하기 2

문제 설명

---

주어진 M×N 크기의 보드에서 K×K 크기의 체스판을 만들려고 한다. 체스판의 색상은 두 가지 패턴 중 하나를 따라야 하며, 검은색과 흰색이 번갈아야 한다. 주어진 보드에서 K×K 체스판을 잘라낸 후, 최소한으로 다시 칠해야 하는 정사각형의 수를 계산하는 문제이다,

---

 

이 문제는 백준의 "단계별 - 누적합" 단계에 속해있는 문제이다. 하지만 이런 형식의 문제를 처음 본다면 이 문제를 어떻게 누적합으로 풀어야할지 잘 모르겠는 경우가 있을 것이다. 어쨋든 이 문제는 2차원 누적합의 응용을 통해 풀 수 있다. 우선 sum[i][j] = "(1, 1) ~ (i, j)정사각형에서 Bst(반복되는 완성된 패턴을 미리 저장해둔 배열)과 map(입력된 배열)의 다른 패턴의 수"라 정의하자.

 

생각을 하다보면, 체스판은 총 2가지 종류로밖에 칠해지지 않는다는 것을 알 수 있다.

=> 첫번째가 'W'인 경우 or 첫번째가 'B'인 경우

 

따라서 가장 처음 해야할 것은 Bst 배열을 초기화하여 체스판 패턴을 생성하는 것이다. 패턴의 시작 색상 C('W', 'B')에 따라 첫 번째 칸을 설정하고, 나머지 칸을 번갈아가며 채운다.

 

그 후, 각 칸의 색칠 필요 여부를 계산하여 누적합 배열 sum을 아까 정의한 대로 업데이트한다.

 

마지막으로, 모든 지점에서 "sum[i][j] - sum[i-k][j] - sum[i][j-k] + sum[i-k][j-k]"중의 최솟값을 구한다.

---

소스 코드

#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

char Bst[2010][2010];
int sum[2010][2010];
int n, m, k;
char map[2010][2010];
int ans = 2e9;

void chess_re_color(char C) {
    int i, j;
    Bst[1][1] = C;
    for(i=2;i<=n;i++) {
        if(Bst[i-1][1] == 'B') Bst[i][1] = 'W';
        else Bst[i][1] = 'B';
    }
    for(i=1;i<=n;i++) {
        for(j=2;j<=m;j++) {
            if(Bst[i][j-1] == 'B') Bst[i][j] = 'W';
            else Bst[i][j] = 'B';
        }
    }
    for(i=1;i<=n;i++) {
        for(j=1;j<=m;j++) {
            int res = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
            if(map[i][j] != Bst[i][j]) res++;
            sum[i][j] = res;
        }
    }
    for(i=k;i<=n;i++) {
        for(j=k;j<=m;j++) {
            int res = sum[i][j] - sum[i-k][j] - sum[i][j-k] + sum[i-k][j-k];
            ans = min(res, ans);
        }
    }
}

int main()
{
    int i;
    scanf("%d %d %d", &n, &m, &k);
    for(i=1;i<=n;i++) {
        scanf("%s", map[i] + 1);
    }
    chess_re_color('B');
    chess_re_color('W');
    printf("%d", ans);
    return 0;
}