백준 - 1018 체스판 다시 칠하기

체스판 다시 칠하기

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

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

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

✔ 접근방법

가능한 모든 경우를 탐색하는 브루트포스 알고리즘을 이용.

1. 입력받은 체스판에서 8*8 부분을 취함
2. 맨왼쪽위 칸에 따라 B_chess, W_chess 의 조건과 현재 부분체스판의 칸을 비교하여 다시 칠해야하는 정사각형의 갯수를 계산
3. 가장 작은 수의 결과값을 출력

✔ 코드

#include <stdio.h>

int main(void){

    int row=0, col=0;
    char board[50][50] = {0,};
    char tmp;
    int r_start=0, c_start=0, count1=0, count2=0, min=999999;
    char check;
    

    scanf("%d %d\n", &row, &col);
    for(int i=0; i<row; i++){
        for( int j=0; j<col; j++){
            while(1){
                tmp = getchar();
                if (tmp != '\n'){
                    board[i][j] = tmp;
                    break;
                }
            }
        }
    }

    /* 전체 체스판에서 8*8 부분 체스판을 취함 */
    for(int i=0; i<=row-8; i++){
        for(int j=0; j<=col-8; j++){
            check = board[i][j]; // 부분 체스판의 맨왼쪽위 칸의 색
            /* 8*8 부분 체스판에서 색이 다른 부분의 갯수를 확인 */
            for(int k=0; k<8; k++){
                for (int l=0; l<8; l++){
                    if ( k%2==0 && l%2==0 ){
                        if( board[i+k][j+l] != check ){ // 맨 왼쪽위 색으로 시작한 체스판
                            count1++;
                        }
                        else{   // 반대의 경우 체스판
                            count2++;
                        }
                    }
                    else if( k%2==0 && l%2==1 ) {
                        if( board[i+k][j+l] == check ){
                            count1++;
                        }
                        else{
                            count2++;
                        }
                    }
                    else if( k%2==1 && l%2==0 ) {
                        if( board[i+k][j+l] == check ){
                            count1++;
                        }
                        else{
                            count2++;
                        }
                    }
                    else if( k%2==1 && l%2==1 ) {
                        if( board[i+k][j+l] != check ){
                            count1++;
                        }
                        else{
                            count2++;
                        }
                    }
                }
            }

            if( count1 <= count2 ){
                if( min > count1 ){
                    min = count1;
                }    
            }
            else{
                if( min > count2 ){
                    min = count2;
                }
            }
            count1 = 0;
            count2 = 0;
        }
    }

    printf("%d\n", min);

    return 0;
}

☝ 팁

• B_chess, W_chess 두가지만 고려하면 되기 때문에 const 로 8*8 체스판을 미리 정의하면 비교하기 편하고 직관적인 코드를 짤 수 있다.

✔ 코드 다시보기

#include <stdio.h>
#include <string>
#include <algorithm>

using namespace std;

const string b_chess[8] = {
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
    };

    const string w_chess[8] = {
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
    };

int main(void){

    int row=0, col=0;
    char board[50][50] = {0,};
    char tmp;
    int r_start=0, c_start=0, count1=0, count2=0, min_result=999999;
    char check;

    scanf("%d %d\n", &row, &col);
    for(int i=0; i<row; i++){
        for( int j=0; j<col; j++){
            while(1){
                tmp = getchar();
                if (tmp != '\n'){
                    board[i][j] = tmp;
                    break;
                }
            }
        }
    }

    /* 전체 체스판에서 8*8 부분 체스판을 취함 */
    for(int i=0; i<=row-8; i++){
        for(int j=0; j<=col-8; j++){
            check = board[i][j]; // 부분 체스판의 맨왼쪽위 칸의 색
            /* 8*8 부분 체스판에서 색이 다른 부분의 갯수를 확인 */
            for(int k=0; k<8; k++){
                for (int l=0; l<8; l++){
                    if( board[i+k][j+l] != b_chess[k][l] ){ count1++; }
                    if( board[i+k][j+l] != w_chess[k][l] ){ count2++; }
                }
            }
            // printf("[check] %d %d\n", count1, count2);
            if (min_result > min(count1, count2)){
                min_result = min(count1, count2);
            }
            count1 = 0;
            count2 = 0;
        }
    }

    printf("%d\n", min_result);

    return 0;
}

👍 참고 사이트

백준 13549 문제