[백준] 1018 체스판 다시 칠하기

문제

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

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

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

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

 

예제 입력 1 

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

예제 출력 1 

 

1

예제 입력 2 

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

예제 출력 2 

12

 

예제 입력 3 

8 8
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

예제 출력 3 

0

예제 입력 4 

9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

예제 출력 4 

31

예제 입력 5 

10 10
BBBBBBBBBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBBBBBBBBB

예제 출력 5 

0

 

예제 입력 6 

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWWWB
BWBWBWBW

예제 출력 6 

2

예제 입력 7 

11 12
BWWBWWBWWBWW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBWWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW

예제 출력 7 

15

 

 

 

 

이 문제는 브루트포싱을 주제로 하는 문제이다.

최적의 경우를 구하는 문제이고, 해당 문제에 적합한 알고리즘이 생각나지 않으므로 브루트포싱이 접근하는데에 있어서 가장 먼저 시도해야 할 알고리즘일 것이다.

 

우선 생각해야 할 점은, 

 

N X M 행열이 주어졌을때,

1.여러개의 8x8 행렬로 나눈다.

2.선택한 8x8 행렬에 대한 문제에서 제시하는 경우의 수를 구한다.

3.모든 행렬에 대한 경우의 수를 비교하여 최적의 경우를 출력한다.

 

현재 정사각행렬인 8x8 행렬을 사용하므로, 행과 열을 같은 간격의 index로 접근하되, spacial locality만 고려해주면 된다.

 

사용자가 행과 열의 값을 N 과 M으로 입력했을때, 

이차원 배열의 행 인덱스는

0 1 2 ... n-8 n-7 n-6 n-5 n-4 n-3 n-2 n-1,

열 인덱스도 마찬가지로  

0 1 2 ... m-8 m-7 m-6 m-5 m-4 m-3 m-2 m-1

와 같은 형태로 접근할 수 있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
//#include <climits> (use if your compiler need it)


int getCases(int row, int col, char **input) {
	int countW = 0;
	int countB = 0;
	// case W
	for (int i = row; i < row + 8 - 1; i+=2) {
		//first row
		for (int j = col; j < col + 8 - 1; j+=2) {
			if (input[i][j] == 'B') {
				//input[i][j] = 'W';
				countW++;
				if (input[i][j + 1] == 'W') {
					//input[i][j + 1] = 'B';
					countW++;
				} 
			}
			else {
				if (input[i][j + 1] == 'W') {
					//input[i][j + 1] = 'B';
					countW++;
				}
			}
		}
		//second row
		for (int j = col; j < col + 8 - 1; j += 2) {
			if (input[i+1][j] == 'W') {
				//input[i+1][j] = 'B';
				countW++;
				if (input[i+1][j + 1] == 'B') {
					//input[i+1][j + 1] = 'W';
					countW++;
				}
			}
			else {
				if (input[i+1][j + 1] == 'B') {
					//input[i+1][j + 1] = 'W';
					countW++;
				}
			}
		}
	}
	// case B
	for (int i = row; i < row + 8 - 1; i += 2) {
		//first row
		for (int j = col; j < col + 8 - 1; j += 2) {
			if (input[i][j] == 'W') {
				//input[i][j] = 'B';
				countB++;
				if (input[i][j + 1] == 'B') {
					//input[i][j + 1] = 'W';
					countB++;
				}
			}
			else {
				if (input[i][j + 1] == 'B') {
					//input[i][j + 1] = 'W';
					countB++;
				}
			}
		}
		//second row
		for (int j = col; j < col + 8 - 1; j += 2) {
			if (input[i + 1][j] == 'B') {
				//input[i + 1][j] = 'W';
				countB++;
				if (input[i + 1][j + 1] == 'W') {
					//input[i + 1][j + 1] = 'B';
					countB++;
				}
			}
			else {
				if (input[i + 1][j + 1] == 'W') {
					//input[i + 1][j + 1] = 'B';
					countB++;
				}
			}
		}
	}
	return countW < countB ? countW : countB;
}

int main(int argc, char* argv[]) {
	int row, col, temp;
	int min = INT_MAX;
	char** input;
	char ch;

	//user input
	scanf("%d %d ", &row, &col);

	//space allocate
	input = (char**)malloc(sizeof(char*) * row);
	for (int i = 0; i < row; i++) {
		input[i] = (char*)malloc(sizeof(char) * col);
	}
	
	//input value
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			ch = getchar();
			if (ch == '\n') {
				ch = getchar();
			}
			input[i][j] = ch;
		}
	}
	
	//func
	for (int i = 0; i <= row - 8; i++) {
		for (int j = 0; j <= col - 8; j++) {
			temp = getCases(i, j, input);
			if (temp < min)
				min = temp;
		}
	}
	printf("%d", min);
    
    	for (int i = 0; i < row; i++) {
		free(input[i]);
	}
	free(input);
    
	return 0;
}

 

 

 

메모리 접근만 신경쓰면 쉽게 해결된다.