백준 c++ 1018번 체스판 다시 칠하기 문제 풀이

문제

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

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

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

 

작성 코드

#include <iostream>
using namespace std;
int main()
{
    int a,b;
    int count1 = 999;
    int count1_=0;
    int count2 = 999;
    int count2_=0;
    cin >> a>> b;
    
    char Basic_Plate[a][b];
    
    char Compare_Plate1[8][8];
    char Compare_Plate2[8][8];
    
    for(int i = 0; i < a; i++){
        cin >> Basic_Plate[i];
    }
    
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
                if(i == 0 && j % 2 == 0){
                Compare_Plate1[i][j] = 'B';
                Compare_Plate2[i][j] = 'W';
                }
                else{
                    Compare_Plate1[i][j] = 'W';
                    Compare_Plate2[i][j] = 'B';
                }
            if(i != 0){
                if(Compare_Plate1[i-1][j] == 'W'){
                    Compare_Plate1[i][j] = 'B';
                }else{
                    Compare_Plate1[i][j] = 'W';
                }
                if(Compare_Plate2[i-1][j] == 'W'){
                    Compare_Plate2[i][j] = 'B';
                }else{
                    Compare_Plate2[i][j] = 'W';
                }
    }}}
    //8*8플레잍
    
    for(int i = 0; i < a-7; i++){
        for(int j = 0; j < b-7; j++){
            for(int k = 0; k < 8; k++){
                for(int q = 0; q<8; q++){
                    if(Basic_Plate[i+k][j+q] == Compare_Plate1[k][q]) count1_++;
                    if(Basic_Plate[i+k][j+q] == Compare_Plate2[k][q]) count2_++;
                }
            }
            if(count1 > count1_) count1 = count1_;
            if(count2 > count2_) count2 = count2_;
            count1_ = 0;
            count2_ = 0;
        }
    }
    
    if(count2 > count1) cout<< count1;
    else cout<<count2;
    return 0;
}

 

입력을 받아온 후 두가지 경우의 수의 8*8판을 만들었다.

for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
                if(i == 0 && j % 2 == 0){
                Compare_Plate1[i][j] = 'B';
                Compare_Plate2[i][j] = 'W';
                }
                else{
                    Compare_Plate1[i][j] = 'W';
                    Compare_Plate2[i][j] = 'B';
                }
            if(i != 0){
                if(Compare_Plate1[i-1][j] == 'W'){
                    Compare_Plate1[i][j] = 'B';
                }else{
                    Compare_Plate1[i][j] = 'W';
                }
                if(Compare_Plate2[i-1][j] == 'W'){
                    Compare_Plate2[i][j] = 'B';
                }else{
                    Compare_Plate2[i][j] = 'W';
                }
    }}}

입력의 시작지점과 끝지점-8까지 비교가능하다 판단하고

시작지점을 for문으로 바꿔가며 비교하였다.

for(int i = 0; i < a-7; i++){
        for(int j = 0; j < b-7; j++){
            for(int k = 0; k < 8; k++){
                for(int q = 0; q<8; q++){
                    if(Basic_Plate[i+k][j+q] == Compare_Plate1[k][q]) count1_++;
                    if(Basic_Plate[i+k][j+q] == Compare_Plate2[k][q]) count2_++;
                }
            }
            if(count1 > count1_) count1 = count1_;
            if(count2 > count2_) count2 = count2_;
            count1_ = 0;
            count2_ = 0;
        }
    }

한번 비교가 끝날때마다 count를 더 작은 수로 업데이트 시켜 주고

count_들을 0으로 초기화하고 반복한다.

if(count2 > count1) cout<< count1;
    else cout<<count2;
    return 0;

마지막에 count1 과 count2를 비교하여 더 작은 숫자를 출력했다.