백준 1018 체스판 다시 칠하기 [BruteForce]

문제 링크: https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

문제 풀이

N X M 판에서, 8 X 8 판을 떼어내서 체스판이 되게 다시 칠해주는 작업을 할 때

그 횟수가 최소가 되는 부분을 찾아내는 문제입니다.

 

문제를 잘게 쪼개서 보면 다음과 같이 정리할 수 있습니다.

1. N X M을 8 X 8의 크기로 잘라낸다. (수많은 체스판들이 나옵니다.)

2. 잘라난 체스판을 가장 왼쪽 위가 흰색인 부분과, 가장 왼쪽 위가 검정색인 부분을 나눈 후 색칠을 합니다.

3. 가장 왼쪽 위가 흰색인 부분의 count와 가장 왼쪽 위가 검쟁색인 부분의 count와 비교해서 더 작은 값을 갱신합니다.

 

copy_a는 가장 왼쪽 위가 흰색이라고 생각하고,

copy_b는 가장 왼쪽 위가 검정색이라고 생각하고 문제에 접근했습니다.

 

* 주의할 점이 가장 왼쪽 위가 흰색인 것과, 가장 왼쪽 위가 검정색인 것의 차이가 있습니다!

둘이 처음에는 저도 같은 값이 나올 줄 알았는데, 실은 다르다는 것입니다.

저도 이 부분은 https://yabmoons.tistory.com/119#comment15736501

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

위의 블로그를 참조하시면 좋을 것 같습니다.

 

또, 이 문제는 최솟값을 찾는 것이 목적이기 때문에 초기 설정을 잘해줘야 정답이 나옵니다.

여기서 최대한 나올 수 있는 값은 32입니다.

체스판 8 X 8이라는 64개의 정사각형에서, 체스판은 흑백 흑백 순으로 나와야 되기 때문에 나올 수 있는 최대의 경우는 32가 됩니다.

 

저는 최대치 계산이 처음에는 잘 몰라서, -1로 해놓고 이후에는 min을 이용해서 갱신했지만

풀고 보니 32 값도 됩니다!

 

소스 코드

#include <iostream>
#include <algorithm>

#define MAX_SIZE 50 + 1
using namespace std;

char a[MAX_SIZE][MAX_SIZE];
char copy_a[8][8];
char copy_b[8][8];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int n, m;

int main()
{
	freopen("input.txt", "r", stdin);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
		}
	}

	int ans = -1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			// (i,j)를 기준으로 8 * 8 크기를 만들 수 있다면
			if (i + 7 < n && j + 7 < m)
			{
				int x = 0, y = 0;
				// copy맵에 복사해놓기
				for (int k = i; k <= i + 7; k++, x++)
				{
					for (int l = j; l <= j + 7; l++, y++)
					{
						copy_a[x][y] = a[k][l];
						copy_b[x][y] = a[k][l];
					}
					y = 0;
				}

				int cnt = 0;
				// 8 * 8 체스판에 필요한 부분을 색칠한다.
				// 가장 왼쪽 위가 흰색인 경우 copy_a
				if (copy_a[0][0] == 'B')
				{
					copy_a[0][0] = 'W';
					cnt++;
				}
				for (int i2 = 0; i2 < 8; i2++)
				{
					for (int j2 = 0; j2 < 8; j2++)
					{
						int cx = i2;
						int cy = j2;
						for (int dir = 0; dir < 4; dir++)
						{
							int nx = cx + dx[dir];
							int ny = cy + dy[dir];
							if (nx >= 0 && ny >= 0 && nx < 8 && ny < 8)
							{
								// 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져야 하므로
								if (copy_a[nx][ny] == copy_a[cx][cy])
								{
									cnt++;
									if (copy_a[cx][cy] == 'B') copy_a[nx][ny] = 'W';
									else copy_a[nx][ny] = 'B';
								}
							}
						}
					}
				}
				if (ans == -1) ans = cnt;
				else ans = min(ans, cnt);

				// 가장 왼쪽 위가 검정색인 경우 copy_b
				cnt = 0;
				if (copy_b[0][0] == 'W')
				{
					copy_b[0][0] = 'B';
					cnt++;
				}

				for (int i2 = 0; i2 < 8; i2++)
				{
					for (int j2 = 0; j2 < 8; j2++)
					{
						int cx = i2;
						int cy = j2;
						for (int dir = 0; dir < 4; dir++)
						{
							int nx = cx + dx[dir];
							int ny = cy + dy[dir];
							if (nx >= 0 && ny >= 0 && nx < 8 && ny < 8)
							{
								// 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져야 하므로
								if (copy_b[nx][ny] == copy_b[cx][cy])
								{
									cnt++;
									if (copy_b[cx][cy] == 'B') copy_b[nx][ny] = 'W';
									else copy_b[nx][ny] = 'B';
								}
							}
						}
					}
				}

				if (ans == -1) ans = cnt;
				else ans = min(ans, cnt);
			}
		}
	}
	cout << ans << '\n';
	return 0;
}