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

백준 온라인 저지(BOJ) 1018번 체스판 다시 칠하기
https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

* 사용언어 : C언어, C++

 

1. 문제

M x N 크기의 보드를 8 x 8 크기로 잘라서 체스판을 만들 때,
다시 칠해야하는 정사각형 개수의 최소값을 출력

 

2. 풀이

2차원 char 배열로 체스판을 입력 받고,
8 * 8 씩 전체 탐색하는 방식으로 구현하여 풀었습니다.
 
각 위치 별로 최소값을 확인할 때는
문제에서 주어진대로 2가지 케이스를 따로 나누어 구현해야 합니다.
1) 맨 왼쪽 위 칸이 흰색인 경우, 2) 검은색인 경우
 
각 케이스에 대해서 어느 칸에 어떤 색을 칠할건지 규칙을 찾는 것이 관건인데,
결론부터 말하자면 [y 좌표와 x 좌표를 더한 값] 이 짝수일 때와 홀수일 때로 나누어 처리하면 됩니다.

아래와 같이 y + x 를 표현한 map 을 보면, 쉽게 이해할 수 있습니다.

회색 칸은 y + x 가 짝수, 즉 (y + x) % 2 == 0

 
그 외 풀이는 단순하니 아래 코드로 설명 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1018_체스판 다시 칠하기
1112KB	0ms
*/
#include <cstdio>

const int LM = 50;
char map[LM][LM];
int n, m, min = 64;

void checkMin(char c, int sy, int sx) {
	int cnt = 0;
	for (int y = sy; y < sy + 8; ++y) {
		for (int x = sx; x < sx + 8; ++x) {
			if ((y + x) % 2 == 0) {
				if (map[y][x] != c) ++cnt;
			}
			else {
				if (map[y][x] == c) ++cnt;
			}
		}
	}
	if (cnt < min) min = cnt;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d %d", &n, &m);
	for (int y = 0; y < n; ++y) scanf("%s", &map[y]);

	for (int y = 0; y < n - 7; ++y) {
		for (int x = 0; x < m - 7; ++x) {
			checkMin('B', y, x);
			checkMin('W', y, x);
		}
	}

	printf("%d\n", min);
	return 0;
}