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

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

int wordCount(vector<string> board, int startIndex_x, int startIndex_y, bool changeStartWord)
{
	char startWord = board[startIndex_x][startIndex_y];

	if (changeStartWord)
	{
		if (startWord == 'B')startWord = 'W';
		else startWord = 'B';		
	}

	int changeWordNum = 0; // 바뀐 단어의 갯수

	for (int p = 0; p < 8; p++)
	{
		for (int q = 0; q < 8; q++)
		{
			char checkWord = board[startIndex_x + p][startIndex_y + q]; // 확인할 단어

			// 짝수번째 줄(행)
			if (p % 2 == 0)
			{
				// 짝수번째 단어(열) -> 시작단어와 동일해야함
				if (q % 2 == 0)
				{
					// 동일하지 않은 경우 바뀔 단어의 숫자 증가
					if (checkWord != startWord)
					{
						changeWordNum++;
					}
				}
				else // 홀수번째 단어(열) -> 시작단어와 달라야함
				{
					// 동일한 경우에 단어가 바뀌어야 함
					if (checkWord == startWord)
					{
						changeWordNum++;
					}
				}
			}
			else // 홀수번째 줄(행)
			{				
				// 홀수번째 단어(열) -> 시작단어와 동일해야함
				if (q % 2 != 0)
				{
					// 동일하지 않은 경우 바뀔 단어의 숫자 증가
					if (checkWord != startWord)
					{
						changeWordNum++;
					}
				}
				else // 짝수번째 단어(열) -> 시작단어와 달라야함
				{
					// 동일한 경우에 단어가 바뀌어야 함
					if (checkWord == startWord)
					{
						changeWordNum++;
					}
				}
			}
		}
	}

	return changeWordNum;
}

int main()
{	
	int result = 9999;

	int N, M;
	cin >> N >> M;

	vector<string> v;

	// 입력 문자 받기
	for (int i = 0; i < N; i++)
	{
		string s;
		cin >> s;

		v.push_back(s);
	}
		
	for (int i = 0; i < N - 7; i++)
	{
		for (int j = 0; j < M - 7; j++)
		{
			char startWord = v[i][j]; // 8x8의 좌상단 단어

			int startB = 0; // B로 시작했을때 바꿔야하는 단어의 수
			int startW = 0; // W로 시작했을때 바꿔야하는 단어의 수

			if (startWord == 'B')
			{
				// 시작단어를 B 그대로 시작하는 경우
				startB = wordCount(v, i, j, false);

				// 시작단어를 W로 바꿔서 시작하는 경우
				startW = wordCount(v, i, j, true);
			}
			else
			{
				// 시작단어를 B 그대로 시작하는 경우
				startB = wordCount(v, i, j, false);

				// 시작단어를 W로 바꿔서 시작하는 경우
				startW = wordCount(v, i, j, true);
			}

			if (startB < startW)
			{
				result = result > startB ? startB : result;
			}
			else
			{
				result = result > startW ? startW : result;
			}
			
		}
	}

	cout << result;

	return 0;
}

---

<풀이과정>

 

1. 입력받은 문자들을 저장함

2. 문자들을 반복하여 검사시작

3. 8x8의 좌상단에 해당되는 startWord가 'B'인 경우와 'W'인 경우를 나눠서 생각한다.

4. 짝수행의 짝수열과, 홀수행의 홀수열은 startWord와 같은 단어어야 하고,

짝수행의 홀수열과, 홀수행의 짝수열은 startWord와 다른 단어가 되어야 한다.

5, 또한 startWord도 바뀌는 경우와 바뀌지 않는 경우를 나눠서 생각해야한다.

6. startWord가 바뀌는 경우와 바뀌지 않는 경우 중에 최소가 되는 경우를 저장하고, result보다 해당 값이 더 작다면 result에 해당 값을 저장한다.

7. 이 과정을 startWord가 될 수 있는 단어들을 반복하면서 최소값을 찾아나간다.

---

 

<코멘트>

이것저것 경우의 수가 많아서 헷갈렸고, 반복문이 이렇게 많이 쓰여도 되는지 의문이었다.(브루트포스여서 괜찮은 듯)

코드를 깔끔하게 하려고 함수를 쓰긴 했는데 아직 지저분한것 같다.

뭔가 더 쉽고 간단하게 풀 수 없을까 찾아봤는데 8x8 보드판을 미리 만들어두고 만들어진 보드판과 비교하면 되는 좋은 방법이 있어서 다시 한번 풀어보았다!

바꾸니깐 코드가 좀 더 깔끔하고 메모리양도 줄어들었다!

---

<추가 소스코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

char arr_B[8][8] = {
		'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
		'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B',
		'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
		'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B',
		'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
		'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B',
		'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
		'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'
};

char arr_W[8][8] = {
		'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B',
		'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
		'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B',
		'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
		'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B',
		'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W',
		'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B',
		'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'
};

int wordCount(vector<string> board, int startIndex_x, int startIndex_y, bool blackStart)
{
	int changeWordNum = 0; // 바뀐 단어의 갯수

	for (int p = 0; p < 8; p++)
	{
		for (int q = 0; q < 8; q++)
		{
			char checkWord = board[startIndex_x + p][startIndex_y + q]; // 확인할 단어

			if (blackStart)
			{
				// 검은색 시작인 경우
				if (checkWord != arr_B[p][q]) changeWordNum++;
			}
			else
			{
				// 하얀색 시작인 경우 
				if (checkWord != arr_W[p][q]) changeWordNum++;
			}
		}
	}

	return changeWordNum;
}

int main()
{	
	int result = 9999;	

	int N, M;
	cin >> N >> M;

	vector<string> v;

	// 입력 문자 받기
	for (int i = 0; i < N; i++)
	{
		string s;
		cin >> s;

		v.push_back(s);
	}
		
	for (int i = 0; i < N - 7; i++)
	{
		for (int j = 0; j < M - 7; j++)
		{
			int startB = 0; // B로 시작했을때 바꿔야하는 단어의 수
			int startW = 0; // W로 시작했을 때 바꿔야하는 단어의 수

			// 시작단어가 B로 시작하는 경우
			startB = wordCount(v, i, j, true);

			// 시작단어가 W로 시작하는 경우
			startW = wordCount(v, i, j, false);

			if (startB < startW)
			{
				result = result > startB ? startB : result;
			}
			else
			{
				result = result > startW ? startW : result;
			}
			
		}
	}

	cout << result;

	return 0;
}