BOJ 1018 - 체스판 다시 칠하기

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

핵심은 전체 보드를 한꺼번에 보지 말고 8×8 부분판 단위로 자르는 것이다. 그러면 경우를 빠짐없이 보면서도 계산량이 충분히 감당된다.

코드

//짜놓고 보니 조금 억지같기도 하고..
#include <iostream>
using namespace std;
 
char chess[50][50];
 
int compare_chess(int plus_i, int plus_j, int choose) {
	
	int chess_count = 0;
 
	for (int i = plus_i; i < 8 + plus_i; i++) {
		choose = (choose + 1) % 2;
 
		for (int j = plus_j; j < 8 + plus_j; j++) {
 
			if (choose == 0) {
				if (chess[i][j] != 'B')
					chess_count++;
			}
			else {
				if (chess[i][j] != 'W')
					chess_count++;
			}
			choose = (choose + 1) % 2;
		}
	}
	return chess_count;
}
 
int main() {
 
	int N, M;
	cin >> N >> M;
 
	int chess_now = 0;
	int chess_now_black = 0;
	int chess_now_white = 0;
	int answer = 64;
 
	for (int i = 0; i < N; i++) 
		for (int j = 0; j < M; j++)
			cin >> chess[i][j];
 
	for (int i = 0; i < N - 7; i++) {
		for (int j = 0; j < M - 7; j++) {
			chess_now_black = compare_chess(i, j, 1);
			chess_now_white = compare_chess(i, j, 0);
			chess_now = (chess_now_black > chess_now_white) ? chess_now_white : chess_now_black;
			answer = (answer > chess_now) ? chess_now : answer;
		}
	}
 
	cout << answer << endl;
 
	return 0;
}

복잡도

시간 복잡도: 가능한 시작 위치마다 고정된 $8 \times 8$ 영역 두 가지를 비교하므로 $O(NM)$ 이다.
공간 복잡도: 입력 보드를 저장하므로 $O(NM)$ 이다.

마무리

8×8 구간마다 시작 색 두 경우만 비교하면 다시 칠해야 할 최소 칸 수가 깔끔하게 나온다.

BOJ 1018 - 체스판 다시 칠하기

문제

입력

출력

풀이

코드

복잡도

마무리

문제#

입력#

출력#

풀이#

코드#

복잡도#

마무리#

문제

입력

출력

풀이

코드

복잡도

마무리