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

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

# 문제 설명

- N*M의 체스판을 입력 받고, 그 중에서 8*8 크기의 체스판으로 자른 후, 변을 공유하는 사각형들이 모두 서로 다른 색이 되도록 칠하고자 한다. 따라서 완성된 체스판은 두 가지의 경우가 있는데, 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우다.

- 체스판을 완성하기 위해 다시 칠해야 하는 체스판의 칸의 개수의 최솟값을 출력한다.

- 첫째 줄에 N과 M이 주어진다. (8<=N,M<=50)

- 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

 

# 풀이 방법

- 완전 탐색

- 입력 받은 체스판을 8*8 부분으로 각각 나누어 보며, 칠해야 하는 칸의 개수를 구한다.

- 8*8 체스판 격자를 미리 chess 배열에 만들어 놓고, 이것과 자른 배열을 비교하며, 다를 경우 cnt에 1을 더하는 방식을 이용하였다.

- 체스판의 종류는 두 가지가 있으므로, s1과 s2에 B와 W의 순서를 저장하여 0,1 값이 두 가지 체스판을 만들 수 있도록 하였다.

 

# 정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int chess[10][10];
char arr[60][60];
string s;
string s1 = "WB";
string s2 = "BW";
int cnt1, cnt2;
int ans = 999;


int main() {

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			chess[i][j] = (i % 2 + j % 2) % 2;
		}
	}

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < m; j++) arr[i][j] = s[j];
	}


	for (int i = 0; i < n - 7; i++) {
		for (int j = 0; j < m - 7; j++) {
			cnt1 = 0;
			cnt2 = 0;
			for (int ii = 0; ii < 8; ii++) {
				for (int jj = 0; jj < 8; jj++) {
					if (arr[i + ii][j + jj] != s1[chess[ii][jj]]) cnt1++;
					if (arr[i + ii][j + jj] != s2[chess[ii][jj]]) cnt2++;
				}
			}
			ans = min(ans, min(cnt1, cnt2));
		}
	}

	cout << ans;
}