25682번: 체스판 다시 칠하기 2

25682번: 체스판 다시 칠하기 2

사용 언어: C++

문제 요약

N*M 크기의 보드. 각 칸은 'B', 'W'로 칠해짐. 이 보드에서 임의의 K*K 크기 부분을 잘라서 체스판처럼 만들고자 한다. 체스판이란, 흑백이 번갈아 있는 형태이며 왼쪽 위 칸이 흰색인 경우와 검은색인 경우 두 가지가 존재한다. 

목표는, K*K 크기의 구간을 선택한 뒤, 체스판으로 만들기 위해 다시 칠해야 하는 정사각형의 최소 개수를 구하는 것이다.

풀이

1. 두 체스판 패턴과 비교

- 입력 보드와 두 체스판 패턴(W 시작, B 시작)을 비교하여 틀린 칸 수를 0과 1로 기록.

- 이를 통해 diff_w[i][j], diff_b[i][j] 배열을 만듦

 

2. 2차원 누적합(prefix sum) 계산

- 각 diff 배열에 대해 2차원 누적합을 만들어서 임의의 K*K 영역에서 바꿔야 할 칸 수를 O(1)에 구할 수 있도록 함

 

3. 모든 K*K 영역에 대해 최소 다시 paint 해야 할 수 계산

- 가능한 모든 K*K 영역을 슬라이딩 윈도우로 탐색하면서, 최소 paint 수 갱신

 

1, 2, 3번 모두 O(NM)으로 통과 가능

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, K;
vector<string> board;

void buildPrefixSum(const vector<vector<int>>& diff, vector<vector<int>>& prefix)
{
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            prefix[i][j] = diff[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
        }
    }
}

int getRegionSum(const vector<vector<int>>& prefix, int x1, int y1)
{
    int x2 = x1 + K;
    int y2 = y1 + K;
    
    return prefix[x2][y2] - prefix[x1][y2] - prefix[x2][y1] + prefix[x1][y1];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M >> K;
    board.resize(N);
    
    for(int i=0; i<N; i++)
    {
        cin >> board[i];
    }
    
    vector<vector<int>> diff_w(N, vector<int>(M)); //왼쪽 위 W
    vector<vector<int>> diff_b(N, vector<int>(M)); //반대
    
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            char expected_w = (!((i + j) % 2)) ? 'W' : 'B';
            char expected_b = (!((i + j) % 2)) ? 'B' : 'W';
            
            diff_w[i][j] = (board[i][j] != expected_w);
            diff_b[i][j] = (board[i][j] != expected_b);
        }
    }
    
    vector<vector<int>> prefix_w(N+1, vector<int>(M+1, 0));
    vector<vector<int>> prefix_b(N+1, vector<int>(M+1, 0));
    buildPrefixSum(diff_w, prefix_w);
    buildPrefixSum(diff_b, prefix_b);
    
    int ans = K*K;
    
    for(int i=0; i<=N-K; i++)
    {
        for(int j=0; j<=M-K; j++)
        {
            int paint_w = getRegionSum(prefix_w, i, j);
            int paint_b = getRegionSum(prefix_b, i, j);
            
            ans = min({ans, paint_b, paint_w});
        }
    }
    
    cout << ans << '\n';
    
    return 0;
}