[BOJ] 25682번 | 체스판 다시 칠하기 2 (C++)

🔗문제 보러가기

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

 

🧑🏻‍💻풀이 과정

1. 각각 N행 M열 크기의 흰색으로 시작하는 보드판과 검은색으로 시작하는 보드판 두 개의 2차원 배열을 준비합니다.
2. 다음 과정을 통해, 교체해야 하는 횟수를 누적하여 저장해 나갑니다.
   • 다음은 올바른 체스판의 배열일 경우를 나타냅니다.
     • (행 + 열)이 짝수일 경우, 시작 색깔(1, 1)과 같아야 한다.
     • (행 + 열)이 홀수일 경우, 시작 색깔(1, 1)과 달라야 한다.
     • 위 두 가지 중 하나에 해당하지 않을 경우, 색깔을 교체해야 한다.
3. 행과 열을 각각 K부터 시작하여, 각각 N, M보다 작거나 같을 때까지 2중 for 문을 돌려가며 다음을 확인합니다.
   • K x K 크기의 보드에서 색깔 변경 횟수를 얻는 방법은 🔗2차원 배열에서 누적합을 얻는 방식과 같습니다.
   • 흰색으로 시작하는 보드판에서 구한 횟수와 검은색으로 시작하는 보드판에서 구한 횟수 중 작은 것을 출력하면 됩니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
using namespace std;
using Board = vector<vector<int>>;
const char WHITE_COLOR = 'W';
const char BLACK_COLOR = 'B';

bool ShouldChangeColor(const char startColor, const char inputColor, const int row, const int col)
{
    bool isEven = (row + col) % 2 == 0;

    // (행 + 열)이 짝수라면, 시작 색(1, 1)과 같아야 올바른 보드판이 된다.
    if (isEven && startColor == inputColor)
        return false;

    // (행 + 열)이 홀수라면, 시작 색(1, 1)과 달라야 올바른 보드판이 된다.
    else if (!isEven && startColor != inputColor)
        return false;
    return true;
}

int main()
{
    FAST_IO;

    int N, M, K;
    cin >> N >> M >> K;

    Board whiteStartBoard(N + 1, vector<int>(M + 1));
    Board blackStartBoard(N + 1, vector<int>(M + 1));

    for (int row = 1; row <= N; row++)
    {
        for (int col = 1; col <= M; col++)
        {
            char color;
            cin >> color;

            bool isChangedInWhiteBoard = ShouldChangeColor(WHITE_COLOR, color, row, col);
            bool isChangedInBlackBoard = ShouldChangeColor(BLACK_COLOR, color, row, col);

            // 이전 누적합 + 새로운 값
            whiteStartBoard[row][col] = whiteStartBoard[row - 1][col] + whiteStartBoard[row][col - 1] - whiteStartBoard[row - 1][col - 1] + isChangedInWhiteBoard;
            blackStartBoard[row][col] = blackStartBoard[row - 1][col] + blackStartBoard[row][col - 1] - blackStartBoard[row - 1][col - 1] + isChangedInBlackBoard;
        }
    }

    int answerInWhiteBoard = 1000000000;
    int answerInBlackBoard = 1000000000;

    for (int row = K; row <= N; row++)
    {
        for (int col = K; col <= M; col++)
        {
            int minInWhiteBoard = whiteStartBoard[row][col] - whiteStartBoard[row - K][col] - whiteStartBoard[row][col - K] + whiteStartBoard[row - K][col - K];
            int minInBlackBoard = blackStartBoard[row][col] - blackStartBoard[row - K][col] - blackStartBoard[row][col - K] + blackStartBoard[row - K][col - K];

            answerInWhiteBoard = min(answerInWhiteBoard, minInWhiteBoard);
            answerInBlackBoard = min(answerInBlackBoard, minInBlackBoard);
        }
    }

    cout << min(answerInWhiteBoard, answerInBlackBoard);
    return 0;
}