[BOJ][1018] 체스판 다시 칠하기

문제

문제 출처

문제 해결 전략

우선 부르트 포스 알고리즘을 사용해야 하는데 가장 어려웠던 것이 범위를 설정하는 것이었다. 쉽게 말해서 입력이 예를 들어서 13x13으로 들어왔다고 가정한다면,
O O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O O O O O O O O O O

O와 0이 저런식으로 계속 움직이면서 범위가 달라지고, 각각 영역에서의 판을 W, B로 바꿔줘야하는 횟수도 각각 다르다 쉽게 말해서 탐색의 범위를 정해주는게 조금 많이 힘들 었던 것 같다.

우선 8x8의 체스판이 나올 경우의 수는 2가지로
첫번째 (0, 0)이 W(흰)이 나오는 경우
두번째 (0, 0)이 B(검)이 나오는 경우
이렇게 두가지 체스판을 결과로 가지게 될 것이다.
각각의 경우에 따라 체스판을 바꿔줘야하는 횟수가 다르게 나올거기 때문이다.

또, 이제 위에서 말한 범위 설정을 해줘야 하는데 이부분을 만들지 못해서 다른 분들의 코드를 참고했다. 인덱스의 끝 정점 예를 들어서 8X8 모양을 가져야 하기 때문에 FOR문의 range를 미리 i+8이 입력 받은 사이즈 보다 작거나 같은 것으로 미리 설정해주면서 판을 움직이듯이 보내고 그 보낸 판을 함수로 호출해서 연산을 해주면 된다! 이해가 잘 되지 않는다면 아래 코드를 보면서 이해를 하면 한결 쉽다!

코드

#include<iostream>
#include<string>
#include<algorithm>
#include<utility>
#define N 50

using namespace std;

string Wfirst[8] = {
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW"
};
string Bfirst[8] = {

	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB"
};

string chess[N];

int Wb_cnt(int x, int y){
	int cnt = 0;
	for(int i = 0;i < 8;i++){
		for(int j = 0;j < 8;j++){
			if(chess[x+i][y+j] != Wfirst[i][j]) cnt++;
		}
	}
	return cnt;
}

int Bw_cnt(int x, int y){
	int cnt = 0;
	for(int i = 0;i < 8;i++){
		for(int j = 0;j < 8;j++){
			if(chess[x+i][y+j] != Bfirst[i][j]) cnt++;
		}
	}
	return cnt;
}

int main(){
	int size[2];
	int cnt;
	int minV = 1000000;
	
	int n, m; cin >> n >> m;
	for(int i = 0;i < n;i++) cin >> chess[i];
	
	for(int i = 0;i+8 <=n;i++){
		for(int j = 0;j + 8 <= m;j++){
			int tmp = min(Wb_cnt(i ,j), Bw_cnt(i ,j));
			if(tmp < minV){
				minV = tmp;
			}
		}
	}
	cout << minV << endl;
}