[C/C++] 백준 1018번 - 체스판 다시 칠하기 (브루트 포스)

 

<코드>

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

int chess[51][51];
/*
black = 0
white = 1
*/

int check(int x,int y)
{
	int cnt1 = 0;
	int cnt2 = 0;

	for (int i = x; i < x + 8; i++) {
		for (int j = y; j < y + 8; j++) {
			if ((i + j) % 2 == chess[i][j]) cnt1++; // 탐색을 시작하는 첫번째 블록이 흰색 일때
			if ((i + j + 1) % 2 == chess[i][j]) cnt2++; // 탐색을 시작하는 첫번째 블록이 검정색 일때
		}
	}

	return min(cnt1, cnt2); // 둘 중 최소값 반환
}

int main()
{
	int N, M;
	int mini = 2500; // 최소 값
	char c;

	cin >> N >> M;

	for (int i = 0; i < N; i++) { // B는 '0', W는 '1'로 저장
		for (int j = 0; j < M; j++) {		
			cin >> c;
			if (c == 'B') chess[i][j] = 0;
			else chess[i][j] = 1;
		}
	}

	for (int i = 0; i <= N-8; i++) { // check(x, y)함수에 탐색을 시작할 인덱스 전달
		for (int j = 0; j <= M-8; j++) {
			if (mini > check(i, j)) mini = check(i, j); // 가장 작은 값인지 판별
		}
	}

	cout << mini;
}

 

 

<chess 배열의 인덱스 예시>

(0,0)	(0,1)	(0,2)	(0,3)	(0,4)	(0,5)	(0,6)	(0,7)
(1,0)	(1,1)	(1,2)	(1,3)	(1,4)	(1,5)	(1,6)	(1,7)
(2,0)	(2,1)	(2,2)	(2,3)	(2,4)	(2,5)	(2,6)	(2,7)
....

 

<chess 배열의 행, 열 인덱스들을 더한 값 예시>

0	1	2	3	4	5	6	7
1	2	3	4	5	6	7	8
2	3	4	5	6	7	8	9
...

체스판과 같이 값들이 짝수, 홀수 번갈아가면서 나온다.

 

위의 문제는 N*M의 크기의 체스판에서 8*8의 크기로 잘라낸 다음 8*8 체스판에서 다시 칠해야 하는 정사각형 수 둘 중 최소 값을 찾는 문제이다. 풀이과정은 먼저 N, M값을 받고 'B'와'W'로 구성된 문자를 '0'과 '1'로 변환하여 chess라는 2차원 배열에 저장하였고, 만들 수 있는 모든 8*8 체스판의 경우들을 계산하기 위해 check(int x, int y) 함수에 탐색을 시작할 인덱스를 전달하는 방식으로 코딩하였다.

 

 

 

 

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

1018번: 체스판 다시 칠하기