백준 1018번 체스판 다시 칠하기 [C++]

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

1018번: 체스판 다시 칠하기

 

주어진 크기의 배열에서 체스판 처럼 칠해진 8x8 크기의 배열을 추출한다고 할 때, 가장 적게 새로 색칠하는 경우의 횟수를 구하면 된다.

 

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

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    char arr[n][m];
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            cin >> arr[i][j];
        }
    }
    
    int minimum = 99999;
    
    for (int i=0;i<n-7;i++){
        for (int j=0;j<m-7;j++){
            int num1= 0;
            int num2 = 0;
            for (int k=i;k<i+8;k++){
                for (int q=j;q<j+8;q++){
                    if((k+q) % 2 == 0 && arr[k][q] == 'W') {
                        num1 += 1;
                    } else if((k+q) % 2 == 1 && arr[k][q] == 'B') {
                        num1 += 1;
                    }

                    if ((k+q) % 2 == 0 && arr[k][q] == 'B') {
                        num2 += 1;
                    } else if((k+q) % 2 == 1 && arr[k][q] == 'W') {
                        num2 += 1;
                    }
                }
            }
            if (minimum > min(num1, num2)) {
                minimum = min(num1, num2);
            }
        }
    }
    cout << minimum;
}

문제에서 8x8크기의 배열을 추출해야 한다 했으므로, 반복문의 범위를 n-7, m-7 까지로 제한하고, 그 내부 반복문은 8번으로 제한한다.

그리고 'W'이 나오면 그 다음은 'B'가 나오는, 이런 방식을 가로세로 동일하게 진행하면 되므로, 이를 확인해주며 새로 색칠해야하는 횟수가 몇 번인지 매 8x8 크기 배열마다 확인하여 가장 작은 값을 찾아낸다.