부르트포스 - 백준 체스판 다시 칠하기 1018

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

큰 체스판을 8*8로 짤라내어 올바른 체스판을 만드는 최소한의 횟수를 찾는 방법이다. 어릴 때 부터 느끼는 것이지만 왜 맨날 문제들은 달력을 찢고 짜르고 붙이고를 반복할까 ㅠㅠ

 

이 문제는 아래와 같은 올바른 체스판을 만드는 방법을 찾아야한다. 

첫 시작점이 B냐 W에 따라서 다른 결과가 나오기 때문에 두가지 경우 중 최소의 경우를 찾아야한다. 

WBWBWBWBWB  BWBWBWBWBW

BWBWBWBWBW  WBWBWBWBWB  

WBWBWBWBWB  BWBWBWBWBW

BWBWBWBWBW  WBWBWBWBWB

WBWBWBWBWB  BWBWBWBWBW

BWBWBWBWBW  WBWBWBWBWB

WBWBWBWBWB  BWBWBWBWBW

BWBWBWBWBW  WBWBWBWBWB

 

그리고 이 point가 올바른지 확인하기 위해서 첫 시작점이 무엇인지에따라 포인트의 widthIndex와 heightIndex의 합이 짝수인가 홀수인가에 따라서 올바른지 확인했다. 확인에서 기존의 값 중 가장 작은 값인지 확인한 후 출력하여 문제를 풀 수 있었다.

 

#include <stdio.h>

int N, M;
char map[53][53];
int widthLimit, heightLimit;
void getMinimum();
int isRightPoint(int widthPoint, int heightPoint);
char startPoint;
int min = 10000000;
int checkChangePoint = 0;

int main(){
	scanf("%d %d", &N, &M);
	widthLimit = M-7;
	heightLimit = N-7;

	for(int j = 0; j < N; j++)
		scanf("%s", &map[j]);					
		
	startPoint = 'W';
	getMinimum();
	startPoint = 'B';
	getMinimum();

	printf("%d", min);

}

void getMinimum(){
	for(int startHeight = 0; startHeight < heightLimit; startHeight++){
		for(int startWidth = 0; startWidth < widthLimit; startWidth++){
			for(int height = startHeight; height < startHeight+8; height++){
				for(int width = startWidth; width < startWidth+8; width++){
					if(!isRightPoint(width, height))
						checkChangePoint+=1;
				}
			}
			if(min > checkChangePoint)
				min = checkChangePoint;
			checkChangePoint = 0;
		}
	}
}

int isRightPoint(int widthPoint, int heightPoint){
	if(startPoint == 'W'){
		if((widthPoint+heightPoint)%2 == 0 && map[heightPoint][widthPoint] == 'W')
			return 1;
		else if((widthPoint+heightPoint)%2 != 0 && map[heightPoint][widthPoint] == 'B')
			return 1;
		else 
			return 0;
	}else if(startPoint == 'B'){
		if((widthPoint+heightPoint)%2 == 0 && map[heightPoint][widthPoint] == 'B')
			return 1;
		else if((widthPoint+heightPoint)%2 != 0 && map[heightPoint][widthPoint] == 'W')
			return 1;
		else 
			return 0;
	}
	return 1;
}