[1018] 체스판 다시 칠하기(C++)

문제

1018번: 체스판 다시 칠하기

 

 

해결 방법

우리가 최종적으로 만들 수 있는 체스판의 경우는 아래와 같이 두 가지가 있다.

이 형태는 chess() 함수를 통해 구현하였다.

 

그리고 아래와 같은 보드를 입력받았다고 하자.

 

그러면 (0, 0) 부터 시작해서 (0, 1), (0, 2) ... (1, 0), (1, 1) ... 이런식으로 시작점을 옮겨가면서 아래와 같이 8x8 크기의 체스판을 찾고,

 

각각의 경우에서 우리가 미리 chess() 함수를 통해 구해놓은 정답과 비교하면서,

다른 칸이 있다면 색칠해줘야 하는 칸으로 간주하고 색칠해야 하는 칸의 개수인 cnt를 증가시킨다.

그런 다음 이 값들 중 최솟값을 찾아 출력하면 끝이다!

 

 

내 코드(C++)

// [1018] 체스판 다시 칠하기
// https://www.acmicpc.net/problem/1018
// 브루트 포스

#include <cstdio>
using namespace std;

char board[51][51];
char w[8][8], b[8][8];

// 시작 칸이 흰색, 검은색인 경우로 나누어 미리 8x8 크기의 체스판 설정(정답)
void chess()
{
    for(int i = 0 ; i < 8 ; i++) {
        for(int j = 0 ; j < 8 ; j++) {
            if((i + j) % 2 == 0) {
                w[i][j] = 'W';
                b[i][j] = 'B';
            }
            else {
                w[i][j] = 'B';
                b[i][j] = 'W';
            }
        }
    }
}

// 해당 위치부터 8x8 크기의 체스판과 정답을 비교하여 색칠해야 하는 체스판 개수 반환
int check(char arr[8][8], int x, int y)
{
    int cnt = 0; // 색칠해야 하는 체스판 개수
    for(int i = 0 ; i < 8 ; i++) {
        for(int j = 0 ; j < 8 ; j++) {
            if(arr[i][j] != board[i + x][j + y]) {
                cnt++;
            }
        }
    }
    return cnt;
}

int main(void)
{
    int n, m, min = 1300, ans = 0;
    scanf("%d %d ", &n, &m);
    for(int i = 0 ; i < n ; i++) {
        scanf("%s", board[i]);
    }

    chess();
    for(int i = 0 ; (n - i) >= 8 ; i++) {
        for(int j = 0 ; (m - j) >= 8 ; j++) {
            // 맨 왼쪽 맨 위 칸이 하얀색인 경우
            if((ans = check(w, i, j)) < min)
                min = ans;

            // 맨 왼쪽 맨 위 칸이 검은색인 경우
            if((ans = check(b, i, j)) < min) 
                min = ans;
        }
    }
    printf("%d\n", min);
}