백준 1018번 체스판 다시 칠하기[C/C++]

1018번: 체스판 다시 칠하기

문제 해결법

해결법1

 흰색으로 시작하는 체스판, 검은색으로 시작하는 체스판 배열을 각각 만들어서 두 배열에서 각각 8x8로 자른 판의 count를 세고 count를 비교하여 더 작은쪽을 출력한다.

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int m, n;
int result = 64; //250;
string board[50]; // == char board[50][50];
string wb[8] =
{
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
};

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

void wbcpr(int x, int y) //0 0
{
	int count = 0;

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (wb[i][j] != board[y+i][x+j]) {
				count++;
			}
		}
	}

	if (count < result) result = count;
}

void bwcpr(int x, int y)
{
	int count = 0;

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (bw[i][j] != board[y + i][x + j]) {
				count++;
			}
		}
	}

	if (count < result) result = count;
}


int main() 
{
	cin >> m >> n; // board크기 입력

	for (int i = 0; i < m; i++) {
		cin >> board[i]; //scanf("%s", board[i]);
	}

	//board cut
	for (int y = 0; y < m - 7; y++) { // 0 < 3  10-7
		for (int x = 0; x < n - 7; x++) { // 0 < 6   13-7
			wbcpr(x, y);
			bwcpr(x, y);
		}
	} 

	printf("%d", result);

	return 0;
}

실수한점

 result를 제일 처음에는 250으로 설정해주었다 50x50의 보드사이즈 때문에 수정해야되는 최대 개수가 250개라고 생각했기 때문인데, 어차피 보드를 8x8크기로 잘라서 사용하기 때문에 64로 설정해주어도 된다.

 

 

해결법2

#include <iostream>
#include <string>

using namespace std;

int main()
{
	int n, m;
	int count, result = 64;
	string board[50];

	cin >> n >> m; //보드판의 세로, 가로 길이

	// 1.전체 보드판 받아오기
	for (int i = 0; i < n; i++) {
		cin >> board[i];
	}
    
	// 2. 흰색 판 기준으로 전체보드판과 값을 비교
	for (int y = 0; y < n-7; y++) {
		for (int x = 0; x < m-7; x++) {
			count = 0;
			for (int i = 0; i < 8; i++) {
				for (int j = 0; j < 8; j++) {
					if ((i % 2 == j % 2 ? 'W' : 'B') == board[i+y][j+x])
						count++;
				}
			}
			result = min(result, count);
			result = min(result, 64 - count);
		}
	}

	cout << result;

	return 0;
}

count += (i % 2 == j % 2 ? 'W' : 'B') == board[i + y][j + x];

이 코드는 체스판의 시작 (0, 0)이 흰색으로 시작하는 것으로 기준을 잡았다. 그리고 i %2 == j % 2의 수식은 w의 위치를 보면 알겠지만 (짝수, 짝수)거나 (홀수, 홀수)인 경우 밖에 없다. 그래서 %2를 통해 짝수, 홀수를 판별하여 (짝수, 짝수) 또는 (홀수, 홀수)인 경우를 'W'라고 가정한 것이다.

 

 

검은색으로 시작하는 체스판의 최소 색칠 개수를 구하기 위하여 밑과 같은 코드가 들어갔다.

result = min(result, 64 - count);

 예를 들어 count가 52라면 64 - 52 = 12이와 같은 수식이 만들어지는데,  64는 전체 개수, 52는 흰색으로 시작하는 기준에서 바꿔야 하는 수, 12는 흰색 시작기준 바꾸지 않아도 되는 수이다.

흰색기준으로 바꾸지 않아도 되는 수는, 검은색 시작 기준으로는 바꾸어야 하는 개수가 될 수 있다.