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

문제

M * N 개의 체스판에서, 8 * 8 만큼을 잘라내려고 한다.

각 칸의 색은 랜덤 하므로, 색을 덧칠할 수 있다.

이때, 각 칸에 올바른 색을 가진 8 * 8 보드판을 만들기 위해 최소한의 덧칠 횟수를 구하라.

 

 

해결 계획

일단 8 * 8이 될 수 있는 모든 경우를 검사하긴 해야겠다고 생각해서 완전 탐색을 생각했다.

 

체스판의 각 칸을 검사하는 로직은 문자열 비교나 플래그를 생각했는데, 코드에 문자열 샘플을 넣기 싫어서 보다 깔끔한 플래그를 선택했다.

 

검사를 시작할 때, 처음을 W로 시작하거나, B로 시작하거나 두 가지의 경우가 있었는데, 진짜 이 두 가지를 따로 검사해야 하나??!

하던 중에 떠오른 아이디어가 있다.

 

총 64칸 중에, 63칸의 잘못된 칸이 있다면, 역으로 생각해서 1칸의 정상적인 칸을 덧칠하면 완성되지 않나?라는 생각이 들었다.

그래서 검사를 한 번만 진행해서 나온 결과 값 a를 덧칠해야 하는 횟수라고 생각하면 다음과 같은 코드로 표현이 가능하다.

$$min (a,\  64 - a)$$

이렇게 검사를 한 번만 하는 방식으로 진행했다.

 

 

시간 복잡도

주어지는 체스판의 최대크기가 50이므로, 해당 판에서 $8 \times 8$을 검사할 수 있는 횟수는 $43 \times 43 = 1,849$이다.

한번 검사할 때 64번 검사하므로 $1849 \times 64 = 118,336$ 정도 되며, 복잡도는 $O(118,336)$ 가 된다.

 

처음 문제를 보고 와 이거 진짜 다 해봐야 하나?? 했지만 막상 118,336이란 숫자를 보니까 괜한 걱정이었다..

 

 

구현

main( )

// Global
char board[55][55] = { 0 };

// Main
int main()
{
	// 1. Get input
	int boardX, boardY;
	scanf("%d %d", &boardY, &boardX);
	
	for (int y = 0; y < boardY; ++y)
	{
		scanf("%s", board[y]);
	}

	// 2. Check board
	int result = INT_MAX;
	for (int y = 0; y <= boardY - 8; ++y)
	{
		for (int x = 0; x <= boardX - 8; ++x)
		{
			result = std::min(result,Check(y, x));
		}
	}

	// 3. Print output
	printf("%d", result);
	return 0;
}

Check( )

// 무조건 안전한 idx라고 가정
int Check(int startY, int startX)
{
	int result = 0;
	bool color = false; // 플래그용 변수

	for (int cy = 0; cy < 8; ++cy)
	{
		for (int cx = 0; cx < 8; ++cx)
		{
			int y = startY + cy;
			int x = startX + cx;

			// 색 뒤집기
			color = !color;

			// 한 가지 기준으로만 검사
			if (color == false && board[y][x] == 'B') continue;
			if (color == true && board[y][x] == 'W') continue;
			
			result++;
		}

		// 줄바뀔 때도 색 뒤집기
		color = !color;
	}

	return std::min(result, 64 - result);
}