1018 체스판 다시 채우기

1.문제 이해

---

M x N 크기의 보드를 8 x 8로 잘랐을 때 다시 칠해야 하는 최소 갯수를 구하는 문제이다.

이런식으로 보드가 들어온다.

2. 문제 해결

---

문제를 보고 처음에는 이렇게 생각했다.

vector를 2중으로 만들어서 보드를 넣어놓고
처음부터 끝까지 돌며
한 칸을 잡고 8 x 8로 확인해 보면 되는거 아닌가?

라고 간단하게만 생각하고 코드를 짜고 예제를 풀어봤지만 몇가지 예제가 풀리지 않았다.

이유는 간단했다.

 

왼쪽 위부터 기준을 잡고 오른쪽 아래로 내려오기에 배열의 범위를 벗어나지 않게 전체 크기에서 -8을 하고 돌아버려 오른쪽 아래의 칸들로는 안해본 것이였다.

 

하지만 그대로 오른쪽 아래 칸들을 기준으로 잡고 실행해 버릴시 배열의 범위를 벗어날 것이 분명했다.

그래서 오른쪽 아래 칸들은 그 칸을 기준으로 왼쪽 위로 비교를 했다.

 

그렇게 예제를 통과하고 문제를 제출했지만 통과는 되지않았다.

 

왜 풀리지 않을까 하며 고민을 한참을 고민한 결과 문제를 찾아냈다.

 

입력으로 8 x 8의 칸이 들어왔을 시 기존 코드로 확인을 하면 제일 왼쪽 위 칸만 기준으로 잡고 돌아버려 그 칸을 제외한 모든 칸을 바꿔야 하는 상황이 생겨버렸다.

 

그래서 나는 그 위치의 칸을 검사할 때 그 문자를 기준으로 한번  다른 문자로 한번 더 검사하여 제출한 결과 성공하였다!

 

3. 소스 코드

---

#include<iostream>
#include<vector>

using namespace std;

vector<vector<char>> arr;

int GetWrongChessBorad(int x, int y);
int RGetWrongChessBorad(int x, int y);
int GetWrongChessBoradWithWorngStart(int x, int y);
int RGetWrongChessBoradWithWorngStart(int x, int y);
int main()
{
	int hor, ver;
	cin >> hor >> ver;
	for (int i = 0; i < hor; i++)
	{
		vector<char> v;
		for (int j = 0; j < ver; j++)
		{
			char c;
			cin >> c;
			v.push_back(c);
		}
		arr.push_back(v);
	}
	int answer = 10000;
	for (int i = 0; i < hor - 7; i++)
	{
		for (int j = 0; j < ver - 7; j++)
		{
			int worngCnt = GetWrongChessBorad(i, j);
			if (answer > worngCnt)
			{
				answer = worngCnt;
			}
			worngCnt = GetWrongChessBoradWithWorngStart(i, j);
			if (answer > worngCnt)
			{
				answer = worngCnt;
			}
		}
	}
	for (int i = hor - 1; i > 6; i--)
	{
		for (int j = ver - 1; j > 6; j--)
		{
			int worngCnt = RGetWrongChessBorad(i, j);
			if (answer > worngCnt)
			{
				answer = worngCnt;
			}
			worngCnt = RGetWrongChessBoradWithWorngStart(i, j);
			if (answer > worngCnt)
			{
				answer = worngCnt;
			}
		}
	}

	cout << answer;
}
int GetWrongChessBorad(int x, int y)
{
	bool isW;
	int num = 0;
	isW = arr[x][y] == 'W';
	for (int i = x; i < x + 8; i++)
	{
		for (int j = y; j < y + 8; j++)
		{
			if (x == i && y == j) continue;
			if (arr[i][j] == (isW ? 'W' : 'B'))
			{
				num++;
			}
			isW = !isW;
		}
		isW = !isW;
	}
	return num;
}

int RGetWrongChessBorad(int x, int y)
{
	bool isW;
	int num = 0;
	isW = arr[x][y] == 'W';
	for (int i = x; i > x - 8; i--)
	{
		for (int j = y; j > y - 8; j--)
		{
			if (x == i && y == j) continue;
			if (arr[i][j] == (isW ? 'W' : 'B'))
			{
				num++;
			}
			isW = !isW;
		}
		isW = !isW;
	}
	return num;
}

int GetWrongChessBoradWithWorngStart(int x, int y)
{
	bool isW;
	int num = 1;
	isW = arr[x][y] != 'W';
	for (int i = x; i < x + 8; i++)
	{
		for (int j = y; j < y + 8; j++)
		{
			if (x == i && y == j) continue;
			if (arr[i][j] == (isW ? 'W' : 'B'))
			{
				num++;
			}
			isW = !isW;
		}
		isW = !isW;
	}
	return num;
}

int RGetWrongChessBoradWithWorngStart(int x, int y)
{
	bool isW;
	int num = 1;
	isW = arr[x][y] != 'W';
	for (int i = x; i > x - 8; i--)
	{
		for (int j = y; j > y - 8; j--)
		{
			if (x == i && y == j) continue;
			if (arr[i][j] == (isW ? 'W' : 'B'))
			{
				num++;
			}
			isW = !isW;
		}
		isW = !isW;
	}
	return num;
}

 

 

---

생각이 되는대로 막구 짜다보니 코드가 굉장히 길어진거 같다.

좀 더 문제를 보고 깊게 생각해봐야겠다