[백준/C++] 25682번: 체스판 다시 칠하기 2

문제

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

---

문제 요약

검은색과 흰색 칸으로 이루어진 M × N 크기의 보드가 주어진다.

 

주어진 보드판을 K × K 크기로 잘라 체스판을 만들려고 할 때, 필요한 최소 색칠 횟수를 출력한다.

 

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다.

---

코드

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

using namespace std;

int n, m, k;

char board[2020][2020];

// (0, 0)이 B 또는 W인 체스판으로 만들 때, 칠해야 하면 1, 아니면 0
int b_board[2020][2020];
int w_board[2020][2020];

int prefix_b[2020][2020];
int prefix_w[2020][2020];

int res = 1e9;

int main() {
    // 입출력 단축 코드
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 입력
    cin >> n >> m >> k;

    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;

        for (int j = 0; j < m; j++) {
            board[i][j] = str[j];
        }
    }

    // b_board 채우기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 해당 좌표가 B이어야 하는 데,
            if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
                // W인 경우
                if (board[i][j] == 'W') {
                    b_board[i][j] = 1;
                }
            }

            // 해당 좌표가 W이어야 하는 데,
            else {
                // B인 경우
                if (board[i][j] == 'B') {
                    b_board[i][j] = 1;
                }
            }
        }
    }

    // w_board 채우기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 해당 좌표가 W이어야 하는 데,
            if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
                // B인 경우
                if (board[i][j] == 'B') {
                    w_board[i][j] = 1;
                }
            }

            // 해당 좌표가 B이어야 하는 데,
            else {
                // W인 경우
                if (board[i][j] == 'W') {
                    w_board[i][j] = 1;
                }
            }
        }
    }

    // prefix 구하기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            prefix_b[i + 1][j + 1] = prefix_b[i][j + 1] + prefix_b[i + 1][j] - prefix_b[i][j] + b_board[i][j];
            prefix_w[i + 1][j + 1] = prefix_w[i][j + 1] + prefix_w[i + 1][j] - prefix_w[i][j] + w_board[i][j];
        }
    }

    // 최소 색칠 횟수 구하기
    for (int i = 0; i <= n - k; i++) {
        for (int j = 0; j <= m - k; j++) {
            int b = prefix_b[i + k][j + k] - prefix_b[i + k][j] - prefix_b[i][j + k] + prefix_b[i][j];
            int w = prefix_w[i + k][j + k] - prefix_w[i + k][j] - prefix_w[i][j + k] + prefix_w[i][j];
            
            res = min(res, min(b, w));
        }
    }



    cout << res;

    return 0;
}

---

코드 설명

1. 보드판 정보를 입력 받고, 2차원 배열 board에 저장한다.

 

2. 2차원 배열 b_board와 w_board를 정의하고, board와 비교하여 각각 구한다.

b_board[i][j]

=> 보드판을 (0, 0)이 검은색인 체스판으로 만들 때, (i, j)의 색을 변경해야하면 1, 아니면 0이다.

w_board[i][j]

=> 보드판을 (0, 0)이 흰색인 체스판으로 만들 때, (i, j)의 색을 변경해야하면 1, 아니면 0이다.

 

3.  2차원 배열 prefix_b와 prefix_w를 정의하고, 2차원 누적합을 이용하여 구한다.

prefix_b[i + 1][j + 1]

=> 보드판을 (0, 0)부터, (i, j)까지 자르고, (0, 0)이 검은색인 체스판으로 만들 때, 필요한 색칠 횟수

prefix_w[i + 1][j + 1]

=> 보드판을 (0, 0)부터, (i, j)까지 자르고, (0, 0)이 흰색인 체스판으로 만들 때, 필요한 색칠 횟수

 

+ 인덱스 범위에서 벗어나는 오류가 발생할 수 있으므로 (i, j)까지의 누적합을 prefix[i + 1][j + 1]에 저장한다.

 

4. k 값에 따라 자를 수 있는 모든 경우를 확인한다.

+ (i, j)부터 (i + k - 1, j + k - 1)까지 누적합을 계산하면 된다.

---

고찰

b_board와 w_board의 (i, j)까지 누적합을 prefix_b와 prefix_w의 (i + 1, j + 1)에 저장했더니 헷갈렸다.

 

계속 print를 통해 각 배열을 출력해보면서, 고민했다.