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

문제 번호: 1018

문제 제목: 체스판 다시 칠하기

문제 주소: https://www.acmicpc.net/problem/1018

문제 내용

M * N 크기의 체스판이 주어졌을 때 8*8 크기로 자른 후 흑백이 교대로 나오도록 칸을 교체해야 하는 갯수가 가장 적은 경우는 몇 개인지 출력한다.

테스트 케이스

8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW	1
8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW	0
8 8 BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB	0
11 8 BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB	32
8 11 BBBBBBBBBBB BBBBBBBBBBB BBBBBBBBBBB BBBBBBBBBBB BBBBBBBBBBB BBBBBBBBBBB BBBBBBBBBBB BBBBBBBBBBB	32

문제 풀이

1. 데이터를 입력 받는다. N을 먼저 입력 받고, M을 그 다음에 입력 받는다.
2. 기준이 되는 8 * 9 사이즈 체스판 배열을 만들어 아래와 같이 초기화한다.
WBWBWBWB - WB 판일 때의 비교 시작
BWBWBWBW - BW 판일 때의 비교 시작
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

3. 입력받은 데이터와 체스판을 !=으로 비교연산 하여 그 합계와 현재 값을 비교한다.
4. 3을 통해 구한 가장 적은 합계를 출력한다.
※ 다른 테스트 케이스는 다 맞는데 11 8, 8 11이 틀린다면 반복문을 돌리는 기준이 잘못됐을 가능성이 높다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_1018()
{
	/*----------기준 체스판----------*/
	char standard[9][8];
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 8; j++)
		{ // i + j가 짝수면 흰색, 홀수면 검정색
			standard[i][j] = (i + j) % 2 ? 'B' : 'W';
		}
	}
	/*----------데이터 입력----------*/
	int N;
	int M;
	cin >> N >> M;
	char** data = new char*[N];
	for (int i = 0; i < N; i++)
	{
		data[i] = new char[M + 1];
		cin >> data[i];
	}
	/*----------비교 시작----------*/
	int changePt = 64;
	for (int i = 0; i <= N - 8 && changePt; i++)
	{// 비교 시작 위치 지정, changePt == 0인 경우 반복문 종료
		for (int j = 0; j <= M - 8 && changePt; j++)
		{
			int valueWB = 0;
			int valueBW = 0;
			for (int m = 0; m < 8; m++)
			{// 비교 진행
				for (int n = 0; n < 8; n++)
				{
					valueWB += standard[m][n] != data[i + m][j + n];
					valueBW += standard[m + 1][n] != data[i + m][j + n];
				}
			}
			changePt = changePt > valueWB ? valueWB : changePt;
			changePt = changePt > valueBW ? valueBW : changePt;
		}
	}
	cout << changePt << endl;
	/*----------메모리 해제----------*/
	for (int i = 0; i < N; i++)
	{
		delete[] data[i];
	}
	delete[] data;
	return;
}