[BOJ] 1018번 | 체스판 다시 칠하기 (C++)

🔗문제 보러가기

1018번: 체스판 다시 칠하기

 

 

문제 설명

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

---

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

 

---

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

 

---

예제 입출력

 

---

풀이 전략

브루트 포스로 풀 수 있는 문제입니다. \(8 \times 8\) 체스판을 만들기 위해, 색깔을 바꿔 칠해야 하는 최소의 경우를 구해야 하는 문제인데, 행(가로)에서 이전 색깔과 다음 색깔이 같으면 안 되고, 열(세로)에서도 같으면 안 됩니다.

 

저는 다음과 같은 규칙을 세워 문제를 풀었습니다.

• 가로로 한 칸씩 순회하면서, 이전 색깔과 현재 보고있는 칸의 색깔이 같을 경우 카운트 증가
• 다음 행으로 넘어갈 경우, 첫 번째 색상이 이전 행의 첫 번째 색상과 같을 경우 카운트 증가

BWBWBWBW   // 마지막으로 저장된 이전 색깔은 W
WBWBWBWB   // 1번행의 첫 번째 색깔(B)와 다른 색이어야 한다. (즉, 이전 행의 마지막 색깔의 색과 같아야함)
........

• 체스의 시작 색상(제일 왼쪽 위)이 다른 색일 경우에도 시뮬레이션 진행
• 전부 순회 후, 가장 최소의 경우의 카운트만 저장 후 출력

 

---

소스 코드 및 결과

#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;

void Search(const vector<string>& field, int startRowIdx, int startColumnIdx, const int chessboardSize, int& minCount)
{
	const int MAX_ROW = field.size();
	const int MAX_COLUMN = field[0].length();

	if (startRowIdx + chessboardSize > MAX_ROW || startColumnIdx + chessboardSize > MAX_COLUMN)
		return;


	map<char, char> getOtherColor{ {'W', 'B'}, {'B', 'W'} };

	for (int testCase = 0; testCase < 2; testCase++)
	{
		int replaceNums = (testCase == 0) ? 0 : 1;
		char preColor = (testCase == 0) ? field[startRowIdx][startColumnIdx] : getOtherColor[field[startRowIdx][startColumnIdx]];

		for (int row = startRowIdx; row < startRowIdx + chessboardSize; row++)
		{
			string compare = field[row];
			int startIdx = (row == startRowIdx) ? startColumnIdx + 1 : startColumnIdx;

			for (int column = startIdx; column < startColumnIdx + chessboardSize; column++)
			{
				if (preColor == compare[column])
				{
					replaceNums++;
					preColor = getOtherColor[compare[column]];
					continue;
				}

				preColor = compare[column];
			}

			preColor = getOtherColor[preColor];
		}

		if (replaceNums < minCount)
			minCount = replaceNums;
	}
}


int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	const int chessboardSize = 8;
	int rowNum, columnNum;
	cin >> rowNum >> columnNum;

	vector<string> field;
	for (int i = 0; i < rowNum; i++)
	{
		string row;
		cin >> row;
		field.push_back(row);
	}

	int answer = 2147483647;
	for (int i = 0; i < rowNum; i++)
		for (int j = 0; j < columnNum; j++)
			Search(field, i, j, chessboardSize, answer);

	cout << answer;
	return 0;
}

반례때문에 억까를 좀 많이 당했습니다...ㅎㅎ