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

백준 단계별로 풀어보기 [브루트포스] 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

 

[풀이]

8*8 체스판을 만들기 위해 다시 칠해야 하는 정사각형의 최소 개수를 구하는 문제이다. 브루트포스 문제로 모든 경우의 수를 검사한다. 체스판의 시작인 맨 왼쪽 위 정사각형이 흰색인 경우 다시 칠해야 하는 정사각형 카운트를 w_cnt로, 검정색인 경우 다시 칠해야 하는 정사각형 카운트를 b_cnt로 해서 가장 작은 min_cnt값을 구한다. 

 

[코드]

#include <iostream>
#include <algorithm>

char board[50][50];

int main() {
	int m, n;
	std::string s;
	std::cin >> m >> n;

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

	int min_cnt = 10000;
	int w_cnt, b_cnt; // 시작이 white, 시작이 black.
	for (int i = 0; i < m - 7; i++) {
		for (int j = 0; j < n - 7; j++) {
			w_cnt = 0, b_cnt = 0;
			for (int k = i; k < i + 8; k++) {
				for (int l = j; l < j + 8; l++) {
					if (k % 2 == 0) {
						if (l % 2 == 0) {
							if(board[k][l] == 'B')
								w_cnt++;
							else
								b_cnt++;
						}
						else if (l % 2 == 1) {
							if(board[k][l] == 'W')
								w_cnt++;
							else
								b_cnt++;
						}
					}
					else if (k % 2 == 1) {
						if (l % 2 == 1) {
							if(board[k][l] == 'B')
								w_cnt++;
							else
								b_cnt++;
						}
						else if (l % 2 == 0) {
							if(board[k][l] == 'W')
								w_cnt++;
							else
								b_cnt++;
						}
					}
				}
			}
		
			if(min_cnt > std::min(w_cnt, b_cnt))
				min_cnt = std::min(w_cnt, b_cnt);
			
		}
	}

	std::cout << min_cnt;
}