[1018] 체스판 다시 칠하기, c++

[1018] 체스판 다시 칠하기

 

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

1018번: 체스판 다시 칠하기

한줄 후기 : 난 초딩때 내가 체스 영재인 줄 알았다.

 

#include <iostream>
#include <algorithm>
using namespace std;
char chess[52][52];
int n, m; 
int check_b(int x, int y){
	int cnt=0;
	if(x+8 > n || y+8 > m){
		return 1000000000;
	}
	for(int i=x; i<x+8; i++){
		for(int j=y; j<y+8; j++){
			if(!(i%2)){
				if(!(j%2)){
					if(chess[i][j] != 'B')	cnt++;
				}
				else{
					if(chess[i][j] != 'W')	cnt++;
				}
			}
			else{
				if(!(j%2)){
					if(chess[i][j] !='W')	cnt++;
				}
				else{
					if(chess[i][j] != 'B')	cnt++;
				}
			}
		}
	}
	return cnt;
}
int check_w(int x, int y){
	int cnt=0;
	if(x+8 > n || y+8 > m){
		return 1000000000;
	}
	for(int i=x; i<x+8; i++){
		for(int j=y; j<y+8; j++){
			if(!(i%2)){
				if(!(j%2)){
					if(chess[i][j] != 'W')	cnt++;
				}
				else{
					if(chess[i][j] != 'B')	cnt++;
				}
			}
			else{
				if(!(j%2)){
					if(chess[i][j] !='B')	cnt++;
				}
				else{
					if(chess[i][j] != 'W')	cnt++;
				}
			}
		}
	}
	return cnt;
}
int main(){
	int a, b, result=1000000000, temp;
	scanf("%d %d", &n, &m);
	for(int i=0; i<n; i++){
		scanf("%s", chess[i]);
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			a = check_b(i,j);
			b = check_w(i,j);
			temp = min(a,b);
			result = min(temp, result);
		}
	}
	printf("%d", result);
	return 0;
}

완전탐색이 그냥 다 검사하는 거라고 만만하게 보면 안된다는 것을 깨달은 하루 ^^,, 체스판 문제 전에 치킨 배달 문제를 풀었다가 결국 난 못풀었어서 .. ㅋ 근데 지혜는 품 대단해

아무튼 체스판 문제는 하얀이가 고른건데 보자마자 진짜 풀기 싫게 생겼다고 느꼈다. 그래도 읽어보면 꽤 어렵진 않은 문제..

8*8 정사각형을 골라서 체스판 처럼 칠하려면 바꿔야 하는 색 개수가 최소 몇개인지 고르면 된다.

주의 할 점은 체스판은 흰색으로 시작할 수도 있고, 검정색으로 시작할 수도 있기 때문에 하나만 생각하면 안되고 두개 다 생각해서 그중에 최소 값을 선택해야한다. 그리고 8*8 정사각형을 선택하는 경우의 수를 모두 비교해봐야 한다.

사실 내 코드가 굉장히 더럽고 긴데 충분히 한 함수 안에 집어 넣을 수 있는 문제 같다. 나는 귀찮아서 그냥 W로 시작하는 함수, B로 시작하는 함수 복붙한거 ㅋㄷ 검사할 때는 행, 열을 홀수/짝수로 나눠서 비교해야 편하다.

또한 인덱스에서 +8을 했을 때 인덱스 범위를 초과할 수 있기 때문에 먼저 검사해주는 것이 중요.

​