[Baekjoon] 1018번: 체스판 다시 칠하기

 

 

 

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

1018번: 체스판 다시 칠하기

 

---

 

문제 해결 과정

착안

주어지는 $M \times N$ 크기의 보드 내에서 $8 \times 8$ 크기 단위의 격자를 이동해가며 체스판을 다시 칠하는 횟수를 모두 구해본 다음(브루트 포스(brute force) 알고리즘), 작은 값이 구해졌을 때마다 갱신하고자 하였다.

 

한편, 체스판을 다시 칠하는 과정에서 가장 위의 왼쪽 칸이 $B$인 경우 다시 칠하는 횟수를 $c_b$와 $W$인 경우 다시 칠하는 횟수를 $c_w$라고 하면, 아래의 식이 성립한다.

$$c_b + c_w = 64$$

따라서, $8 \times 8$ 크기의 체스판에 대해 $c_b$의 값만을 계산하여 $c_b$와 $(64 - c_b)$ 중 작은 값을 구하여 현재까지 계산된 값 중 가장 작은 값과 비교하여 갱신하고자 하였다.

 

구현

문제 자체를 해결하는 건 어렵지는 않았는데 위의 식을 발견해 적용하여 연산 횟수와 코드를 깔끔하게 줄이는 것이 생각보다 어려웠다(처음 문제를 해결할 때 위 관계식을 모르고 중복해서 계산하였음... 그래도 문제는 풀리긴 했으나 비효율적인 것 같아서 문제를 더 살펴보다가 알아냈다).

 

문제를 해결하기 위해 체스판의 가장 좌측 상단이 $B$라고 가정했을 때 그 칸으로부터 홀수만큼 거리가 떨어진 칸은 $W$여야 하므로, 체스판을 다시 칠하는 횟수를 계산하는 부분의 코드를 처음에 아래와 같이 작성하였다.

// board[m][n]: 8 * 8 크기의 체스판의 가장 좌측 상단
// i: 세로 방향 인덱스
// j: 가로 방향 인덱스
// count1: 좌측 상단이 'B'일 때 체스판을 다시 칠하는 횟수
// count2: 좌측 상단이 'W'일 때 체스판을 다시 칠하는 횟수


// 가장 좌측 상단으로부터 홀수 거리인지, 아닌지를 판단
if ((i + j) & 1)
{
	// 홀수 거리이면서
	if (board[m + i][n + j] == 'B')
		count1++;	// 현재 칸이 'B'인 경우
	else
		count2++;	// 현재 칸이 'W'인 경우
}
else
{
	// 짝수 거리이면서
	if (board[m + i][n + j] == 'W')
		count1++;	// 현재 칸이 'W'인 경우
	else
		count2++;	// 현재 칸이 'B'인 경우
}

 

어차피 count1과 count2를 합하면 반드시 64가 나올 수 밖에 없기 때문에 이를 이용하면 count2를 굳이 계산하지 않아도 알 수 있다.

 

한편, 다른 분의 코드를 참고하다 XOR 연산자를 사용하는 코드를 봤는데, XOR 연산자를 사용하면 위와 정확하게 동일한 동작을 하는 코드를 더 간단하게 작성할 수 있다. 평소에는 그닥 많이 사용하지 않게 되는 연산자여서 코드를 작성할 때 간과하고 있었던 점이 아쉬웠다.

// 좌측 상단으로부터의 거리가 홀수이면서 'B'일 때, 또는
// 좌측 상단으로부터의 거리가 짝수이면서 'W'일 때만 count를 증가

if ((board[m + i][n + j] == 'W') ^ ((i + j) & 1))
	count++;

 

이 두 가지 테크닉을 활용하여 최종적인 코드를 작성하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int Paint(char board[][51], int m, int n)
{
	int count = 0;

	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			if ((board[m + i][n + j] == 'W') ^ ((i + j) & 1))
				count++;

	return count > 64 - count ? 64 - count : count;
}

int main()
{
	int M, N;
	cin >> M >> N;

	char ChessBoard[51][51] = { 0, };

	for (int i = 0; i < M; i++)
		for (int j = 0; j < N; j++)
			cin >> ChessBoard[i][j];

	int result = 32;
	for (int i = 0; i < M - 7; i++)
		for (int j = 0; j < N - 7; j++)
		{
			if (int paint = Paint(ChessBoard, i, j))
			{
				if (paint < result)
					result = paint;
				continue;
			}
			
			cout << "0\n";
			return 0;
		}
	
	cout << result << "\n";
	return 0;
}

 

실행 결과