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

백준 1018번 c언어 문제풀이

문제:

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

작성 코드

#include <stdio.h>

int main(){
    int x;  
    int y;
    char arr[50][51];
    int cnt1 = 0;
    int cnt2 = 0;
    int count =3000;
    scanf("%d %d",&x,&y);
    
    for(int i=0; i<x; i++){
        scanf("%s",&arr[i]);
    }
    for(int i=0; i<x-7; i++){
        for(int j=0; j<y-7; j++){   //반복문을 통해 8*8 체스판 자르는 것, 이 반복문의 횟수 만큼 자를 수 있음.
            //체스판 형태
            //(짝,짝)(짝,홀)(짝,짝)                     (짝)(홀)(짝)
            //(홀,짝)(홀,홀)(홀,짝)  --> 좌표의 합 표시  (홀)(짝)(홀) --> 좌표의 합이 정상 체스판처럼 배치 되어있다는 것을 알수 있음   
            //(짝,짝)(짝,홀)(짝,짝)                     (짝)(홀)(짝)
            //체스판이라면 두 좌표의 합이 짝수 일때 흰색칸이면, 합이 홀수인 칸은 검정칸, 반대면 반대 경우 적용.
            //시작을 무슨 색으로 하는지 기준으로 두는 것이 아니라 짝수칸 홀수 칸에 어떤색을 칠할지 기준으로 둔다.
            for(int a= i; a< i+8; a++){  
                for(int b=j; b< j+8; b++){ // 이 반복문은 (0,0)부터 검사 시작하면서 시작점 좌표 옮기기. 그리고 합이 짝수칸인경우에 흰색 칠하는 경우
                    if((a + b) % 2 == 0){ //체스판 위치 확인, 합이 짝수칸이라면
                        if(arr[a][b] !='W') //짝수 칸이 흰색이 아니라면 다시칠하기
                            cnt1++;
                    }
                    else{                   //홀수 칸인데
                        if(arr[a][b] != 'B')// 검정이 아니면 다시칠하기
                            cnt1++;
                    }
                }
            }        
            //아래 경우는 이제 좌표의 합이 짝수인 칸을 검정으로 칠하는 경우 위와는 반대인 경우
            for(int a= i; a< i+8; a++){ 
                for(int b=j; b< j+8; b++){
                    if((a + b) % 2 == 0){
                        if(arr[a][b] != 'B') //다시칠하기
                            cnt2++;
                    }
                    else{
                        if(arr[a][b] != 'W')
                            cnt2++;
                    }
                }
            }   
            int result = 0;
            if(cnt1 < cnt2){
            result = cnt1;              //위의 두가지 경우 비교해서 둘중 작은 경우 result에 저장
            } else{
                result = cnt2;
            }
            
            if(count > result){
                count = result;    //count 와 result 비교해서 더 작은 값을 count 값 안에 업데이트 
            }
            cnt1 = 0;
            cnt2 = 0;           //다시 반복문을 돌리기 위해 두가지 경우의 카운트 값 0으로 초기화

        }
    }
    printf("%d", count);  //위 반복문이 끝나고 마지막에 남은 결과 값 프린트
    return 0;
}

참고 하시기 바랍니다. 주석으로 설명 달아놨습니다. 질문있으시다면 댓글 부탁드립니다.