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

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

1018번: 체스판 다시 칠하기

C

#include <stdio.h>

int minValue = 64;
char arr[51][51];

int count(int cnt, int check, char std, int n, int m)
{
	for (int i = n; i < n + 8; i++)
	{
		for (int j = m; j < m + 8; j++)
		{
			if ((i + j) % 2 == check)
			{
				if (std != arr[i][j]) cnt++;
			}
			else
			{
				if (std == arr[i][j]) cnt++;
			}
		}
	}
	return cnt;
}

void findMin(int n, int m)
{
	int check = (n + m) % 2, num1, num2;
	char change = (arr[n][m] == 'B') ? 'W' : 'B';

	num1 = count(0, check, arr[n][m], n, m);
	num2 = count(0, check, change, n, m);

	if (num1 <  minValue)  minValue = num1;
	if (num2 <  minValue)  minValue = num2;
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) scanf("%s", &arr[i]);
	for (int i = 0; i <= n - 8; i++) for (int j = 0; j <= m - 8; j++) findMin(i, j);

	printf("%d",  minValue);
	return 0;
}

C++

#include <iostream>
using namespace std;

int minValue = 64;
char arr[51][51];

int count(int check, char std, int n, int m)
{
	int cnt = 0;
	for (int i = n; i < n + 8; i++)
	{
		for (int j = m; j < m + 8; j++)
		{
			if ((i + j) % 2 == check)
			{
				if (std != arr[i][j]) cnt++;
			}
			else
			{
				if (std == arr[i][j]) cnt++;
			}
		}
	}
	return cnt;
}

void findMin(int n, int m)
{
	int check = (n + m) % 2, num1, num2;
	char change = (arr[n][m] == 'B') ? 'W' : 'B';
	
	num1 = count(check, arr[n][m], n, m);
	num2 = count(check, change, n, m);

	if (num1 < minValue) minValue = num1;
	if (num2 < minValue) minValue = num2;
}

int main()
{
	int n,m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) for (int j=0; j<m; j++) cin >> arr[i][j];
	for (int i = 0; i <= n - 8; i++) for (int j = 0; j <= m - 8; j++) findMin(i, j);

	cout << minValue;
	return 0;
}

코드 설명

main함수
int로 n,m을 선언한 후 n,m을 입력받는다. 반복문을 이용해서 보드의 상태를 입력받는다.
이후 다시 반복문을 사용해서 보드에서 8*8 크기가 되는 영역을 전부 검사한다. 반복문이 끝나면 문제에서 구하라고 한 minValue를 출력하고 프로그램을 종료한다.

findMin함수
체크판은 검은색과 흰색이 번갈아가며 칠해져 있어야 한다. 아래 그림을 보면 알겠지만 같은 색의 경우 (행번호+열번호)%2의 값이 같다. 이를 이용해서 count함수에서 색칠할 횟수를 구할 것이다. 현재 입력된 값의 행 번호와 열 번호를 더한 후 2로 나눈 나머지를 check에 저장한다.

(0,0)이 흰색인 경우도 마찬가지이다.

내 코드에서 기준이 되는 값은 (0,0)의 색이다. num1은 (0,0)의 색을 유지한 상황에서 구한 횟수를 구할 것이고, num2은 (0,0)의 색을 칠하고(B이면 W로, W이면 B로 변경한다.) 칠한 상태에서 색칠 횟수를 구하는 것이다.

num1, num2, minValue를 비교해서 최솟값을 minValue에 저장한다.

count 함수
체스판에서 다시 칠할 횟수를 구하는 함수이다. 위의 표에서 (0,0)에 해당하는 인덱스를 매개변수로 받는다. 이때 findMax에서 구한 check도 받아와서 (0,0)의 색과 같아야 할 부분이 같은지(if문), 달라야 할 부분이 다른지(else문)를 확인하고 그렇지 않을 경우 cnt를 증가시킨다. 체크판을 다 확인한 후에는 cnt를 반환한다.

느낀 점

모든 경우의 수를 검사하는 브루트포스 알고리즘을 활용하는 문제이다. 아이디어 자체는 금방 생각했으나 (0,0)의 값을 바꿔서 확인하는 작업이 필요한 것을 생각하지 못했다. 예제4의 값이 올바르게 나오지 않아 num2를 구해서 비교하는 과정을 추가하니 바로 통과했다.