백준 1018 체스판 다시 칠하기 / C++

문제 : 1018

풀이 point

$N*M$ 내에서 $8*8$ 크기의 체스판을 모두 찾아 최소로 바꾸는 횟수의 경우의 수를 모두 비교해보면 된다.

풀이 방법

B로 시작할 때 체스판 변경 횟수
W로 시작할 때 체스판 변경 횟수
$8*8$ 경우의 수 찾아보기

코드

//백준 1018, 체스판 다시 칠하기

#include <iostream>
#include <algorithm>

int M, N;
char grid[51][51];

int checkB(int i, int j){
    int change{0};
    for(int x{i}; x<i+8; ++x){
        for(int y{j}; y<j+8; ++y){
            if(x%2 != 0 && y%2 != 0 && grid[x][y] != 'B'){
                ++change;
            }
            else if(x%2 != 0 && y%2 == 0 && grid[x][y] != 'W'){
                ++change;
            }
            else if(x%2 == 0 && y%2 == 0 && grid[x][y] != 'B'){
                ++change;
            }
            else if(x%2 == 0 && y%2 != 0 && grid[x][y] != 'W'){
                ++change;
            }
        }
    }
    return change;
}

int checkW(int i, int j){
    int change{0};
    for(int x{i}; x<i+8; ++x){
        for(int y{j}; y<j+8; ++y){
            if(x%2 != 0 && y%2 != 0 && grid[x][y] != 'W'){
                ++change;
            }
            else if(x%2 != 0 && y%2 == 0 && grid[x][y] != 'B'){
                ++change;
            }
            else if(x%2 == 0 && y%2 == 0 && grid[x][y] != 'W'){
                ++change;
            }
            else if(x%2 == 0 && y%2 != 0 && grid[x][y] != 'B'){
                ++change;
            }
        }
    }
    return change;
}

int main (){

    std::cin >> N >> M;
    for(int i{1}; i<=N; ++i){
        std::string row;
        std::cin >> row;
        for(int j{1}; j<=M; ++j){
            grid[i][j] = row[j-1];
        }
    }

    int min{99999};
    for(int i{1}; i<=N-8+1; ++i){
        for(int j{1}; j<=M-8+1; ++j){
            min = std::min(checkB(i, j), min);
            min = std::min(checkW(i, j), min);
        }
    }

    std::cout << min;

    return 0;
}

사족

W로 시작하면 W
B로 시작하면 B만 탐색하도록 했는데 착오였다.
W로 시작한다고 해서 W로 시작하는 방법이 최소가 아닐 수도 있기 때문이다.

2025-01-18T04:58:50.237Z