백준 1018번: 체스판 다시 칠하기 (C++)

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

1018번: 체스판 다시 칠하기

 

 

풀이

완전 탐색 문제.

전부 체크해야만 알 수 있는 문제인데 체크 방법을 고민했다.

 

나는 B로 시작하는 체스판과 W로 시작하는 체스판을 미리 만들어 놓고 비교하는 식으로 구현했다.

어처피 8 * 8이라서 시간 복잡도 문제가 생기지 않을 거 같았고 B, W 보드와 비교 후 둘 중 작은 값을 갱신해가며 탐색을 진행했다.

 

전체 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	char board[51][51];
	char board_B[51][51];
	char board_W[51][51];
	int minN = 987654321;

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
			if ((i + j) % 2) { //홀수일때
				board_B[i][j] = 'W'; 
				board_W[i][j] = 'B';
			}
			else { //짝수일때
				board_B[i][j] = 'B';
				board_W[i][j] = 'W';
			}
		}
	}

	for (int i = 0; i < N - 7; i++) {
		for (int j = 0; j < M - 7; j++) {
			int diff_B = 0;
			int diff_W = 0;
			for (int k = i; k < i + 8; k++) {
				for (int l = j; l < j + 8; l++) {
					if (board[k][l] != board_B[k][l]) diff_B++;
					if (board[k][l] != board_W[k][l]) diff_W++;
				}
			}
			int tmp = min(diff_B, diff_W);
			minN = min(minN, tmp);
		}
	}

	cout << minN;

}