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

#문제

#풀이

#include <iostream>

using namespace std;

char board[50][50];
int n, m, minNum(64);

char wb[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'},
};

char bw[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'},
};

void checkWb(int x, int y)
{
	int cnt = 0;

	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			if (wb[i][j] == board[i + x][j + y])
			{
				cnt++;
			}
		}
	}

	if (cnt < minNum)
	{
		minNum = cnt;
	}
}

void checkBw(int x, int y)
{
	int cnt = 0;

	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			if (bw[i][j] == board[i + x][j + y])
			{
				cnt++;
			}
		}
	}

	if (cnt < minNum)
	{
		minNum = cnt;
	}
}

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

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			char c;
			cin >> c;

			board[i][j] = c;
		}
	}

	for (int i = 0; i < n - 7; ++i)
	{
		for (int j = 0; j < m - 7; ++j)
		{
			checkWb(i, j);
			checkBw(i, j);
		}
	}

	cout << minNum;

	return 0;
}

#정리

흰색, 검은색 타일이 연속된 최대 50x50 보드에서 8x8 크기를 잘라낸 후, 체스판으로 만드는 데 필요한 최소 비용을 구하는 문제이다. 나는 부르트포스를 이용해 (0, 0)부터 (N-7, M-7)까지 8x8의 범위를 최소 비용의 타일맵과 비교하여 문제를 해결했다. 비교 방법에 대해 고민을 많이 했다. NxM 보드에서 0-8, 1-9, 2-10… 까지 8개씩 끊어서 비교하는 방법, 그리고 비교타겟은 0-8인데, board의 1-9의 타일을 어떻게 비교할 것인지에 대해 고민했다. 풀고나니 간단했다. 함수를 떼어내 시작 숫자를 더하여 해결했다.

#문제

#풀이

#정리

Enjoy Reading This Article?