[BOJ-25682][C++] 체스판 다시 칠하기 2

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 K×K 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

 

출력

첫째 줄에 지민이가 잘라낸 K×K 보드를 체스판으로 만들기 위해 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

 

제한

• 1 ≤ N, M ≤ 2000
• 1 ≤ K ≤ min(N, M)

 

예제 입력 1

4 4 3
BBBB
BBBB
BBBW
BBWB

 

예제 출력 1

2

 

예제 입력 2

8 8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

 

예제 출력 2

1

 

예제 입력 3

10 13 10
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

 

예제 출력 3

30

 

예제 입력 4

9 23 9
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBWWWWWWWW

 

문제 출처

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

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

 

---

 

문제 해결 방법

• 2차원 배열 누적 합 알고리즘을 이용하여 어렵게 풀었던 문제였다.
• 문제 해결을 위해 내가 접근했던 방법의 핵심은 다음과 같다.

시작점(왼쪽 대각선 상단)의 색상(@startColor@)이 다른 N × M 크기의 체스판을 각각 만든 후(시작점의 색상이 흰색(W)인 체스판을 A, 검정색(B)인 체스판을 B라고 하자.), 각각의 A, B 체스판을 입력 받은 N × M 크기의 체스판(C 체스판이라고 하자.)과 비교한다. 그리고 색상이 다른 부분의 수를 카운팅하여 A 체스판과 C 체스판의 다른 색상 수, B 체스판과 C 체스판의 다른 색상 수 중 최솟값을 출력한다. 이 때, 다른 부분의 색상 수를 카운팅 하기 위해서 2차원 배열 누적 합 알고리즘을 이용한다.

체스판 A(왼쪽)와 체스판 B(오른쪽)

 

예제 입력을 통해 문제 이해하기

• 문제의 @예제 입력 1@을 통해 이해해보자.

예제 입력과 체스판 C, 체스판 A, 체스판 B를 나타낸 그림

• 체스판 A의 시작점은 흰색(@W@)이며, 흰색이 있는 부분은 @(행번호+열번호) % 2 == 0@를 만족한다.
• 체스판 B의 시작점은 검정색(@B@)이며, 검정색이 있는 부분은 @(행번호+열번호) % 2 != 0@를 만족한다.
• 체스판 C는 문제에서 입력 받은 4 × 4 크기의 체스판이다.

 

체스판 A와 체스판 C 비교하기

체스판 C와 체스판 A의 각 부분을 비교한 후, 부분 합을 구하고 3x3 구간(K=3)에서 최솟값을 구한다.

• 체스판 C와 체스판 A의 각 값들을 비교한다.
  • 서로 다른 색상일 경우 1로, 서로 같은 색상일 경우 0으로 체크한다. (@value@)
• 그리고 3(N) × 3(M) 크기의 부분 합 배열(@pSum@)을 채워 나간다.
• 그리고 나서 이 부분 합 배열(@pSum@)의 내부를 3 × 3 크기씩 움직이면서 최솟값을 탐색한다. 이 때, 가장 작은 최솟값은 5이다.

 

반응형

 

체스판 B와 체스판 C 비교하기

체스판 C와 체스판 B의 각 부분을 비교한 후, 부분 합을 구하고 3x3 구간(K=3)에서 최솟값을 구한다.

• 체스판 C와 체스판 B의 각 값들을 비교한다.
  • 서로 다른 색상일 경우 1로, 서로 같은 색상일 경우 0으로 체크한다. (@value@)
• 그리고 3(N) × 3(M) 크기의 부분 합 배열(@pSum@)을 채워 나간다.
• 그리고 나서 이 부분 합 배열(@pSum@)의 내부를 3 × 3 크기씩 움직이면서 최솟값을 탐색한다. 이 때, 가장 작은 최솟값은 2이다.

 

최솟값 비교 및 정답 출력하기

• 체스판 A와 체스판 C의 다른 색상 수와 체스판 B와 체스판 C의 다른 색상 수 중 더 작은 값(최솟값)이 이 문제의 정답이 된다.
  
  • 이 말은 즉, 입력 받은 체스판(체스판 C)을 시작점이 흰색(W)인 체스판(체스판 A)과 시작점이 검정색(B)인 체스판(체스판 B)과 각각 비교하는데, 각각 도출된 서로 다른 색상 수 중에서 최솟값을 구한다는 것이다.
• 이 과정들을 코드로 작성하면 다음과 같다.

int Solution(char startColor) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if ((i + j) % 2 == 0) {
                if (board[i][j] == startColor) {
                    value = 0;
                }
                else {
                    value = 1;
                }
            }
            else {
                if (board[i][j] == startColor) {
                    value = 1;
                }
                else {
                    value = 0;
                }
            }
            
            // 부분 합 구하기
            pSum[i][j] = pSum[i][j - 1] + pSum[i - 1][j] - pSum[i - 1][j - 1] + value;
        }
    }
    
    int count = INT_MAX;
    
    for (int i = 1; i <= N - K + 1; i++) {
        for (int j = 1; j <= M - K + 1; j++) {
            // K*K 구간의 누적 합의 최솟값 구하기
            count = min(count, pSum[i + K - 1][j + K - 1] - (pSum[i + K - 1][j - 1] + pSum[i - 1][j + K - 1]) + pSum[i - 1][j - 1]);
        }
    }
    return count;
}

void Output() {
    cout << min(Solution('W'), Solution('B')) << '\n';
}

 

코드

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int N, M, K, value;
char board[2001][2001];
int pSum[2001][2001];

void Input() {
    cin >> N >> M >> K;
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> board[i][j];
        }
    }
}

int Solution(char startColor) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if ((i + j) % 2 == 0) {
                if (board[i][j] == startColor) {
                    value = 0;
                }
                else {
                    value = 1;
                }
            }
            else {
                if (board[i][j] == startColor) {
                    value = 1;
                }
                else {
                    value = 0;
                }
            }
            
            // 부분 합 구하기
            pSum[i][j] = pSum[i][j - 1] + pSum[i - 1][j] - pSum[i - 1][j - 1] + value;
        }
    }
    
    int count = INT_MAX;
    
    for (int i = 1; i <= N - K + 1; i++) {
        for (int j = 1; j <= M - K + 1; j++) {
            // K*K 구간의 누적 합의 최솟값 구하기
            count = min(count, pSum[i + K - 1][j + K - 1] - (pSum[i + K - 1][j - 1] + pSum[i - 1][j + K - 1]) + pSum[i - 1][j - 1]);
        }
    }
    return count;
}

void Output() {
    cout << min(Solution('W'), Solution('B')) << '\n';
}

void Solve() {
    Input();
    Output();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    Solve();
    
    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [구간 합]
• 골드V

 

2차원 배열에서 누적 합(부분 합) 구하기

알고리즘

void PrefixSum2DArray() {
    cin >> N >> M;

    // 표 채우기 (N x M)
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= M; c++) {
            cin >> matrix[r][c];
            pSum[r][c] = pSum[r - 1][c] + pSum[r][c - 1] - pSum[r - 1][c - 1] + matrix[r][c];
        }
    }

    cin >> K;

    // 구해야 하는 좌표 입력 받기 : (x1, y1), (x2, y2)
    for (int i = 1; i <= K; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        
        cout << pSum[x2][y2] - (pSum[x1 - 1][y2] + pSum[x2][y1 - 1]) + pSum[x1 - 1][y1 - 1] << '\n';
    }
}