백준 1018 체스판 다시 칠하기

 

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

1018번: 체스판 다시 칠하기

 

 

서론

 

풀이 결과에 반례가 발생. 

접근방식에 문제가 있었다.

좌측 상단 글자를 기준으로 다른 글자들이 바르게 위치해있는지 검사했는데,

 

BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

 

이런 예제에서 {0,0}의 B가 맞다고 가정하고 검사를 하기 때문에, {0,0}을 제외한 모든 글자를 수정하여 답이 63이 나온다.

실제 답은 {0,0}의 B만 W로 수정하면 되기때문에 1이다.

찾는데 오래걸렸다.

 

풀이

 

1.

일단 예제1과 같은 n=8, m=8일때

 

 

0	1	0	1	0	1	0	1
1	0	1	0	1	0	1	0
0	1	0	1	0	1	0	1
1	0	1	0	1	0	1	0
0	1	0	1	0	1	0	1
1	0	1	0	1	0	1	0
0	1	0	1	0	1	0	1
1	0	1	0	1	0	1	0

 

 

checker변수를 통해서 체스판을 1과 0 구역으로 구분시킨다.

변수가 0과 1만 나오는 방법은 변수%=2를 쓴다.

 

(1) 0구역이 B이거나 1구역이 W면 sumW를 증가시킨다.

 

 

BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW	WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB
sumW : 64	sumW : 0

 

 

오른쪽 예제는 정답을 출력하지만 왼쪽예제는 정답을 출력하지 못한다. 그래서

 

(2) 0구역이 W이이거나 1구역이 B면 sumB를 증가시킨다.

 

 

BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW	WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW  WBWBWBWB
sumB : 0	sumB : 64

 

 

왼쪽 예제는 정답을 출력하지만 오른쪽예제는 정답을 출력하지 못한다.

 

그래서 sumB와 sumW의 최솟값이 정답이 된다. 

 

2.

1번 과정을 왼쪽 상단 좌표를 기준으로 (0,0)부터 (n,m)까지 모두 확인하여 그 중 최소값을 출력하면 된다.

 

구현

 

//c++

#include <iostream>
#include <algorithm>

using namespace std;

char board[51][51];
int n, m;
int result = 51*51;

void search(int y, int x) {
	if (y + 8 > n || x + 8 > m) return;

	int sumw = 0;
	int sumb = 0;
	int sum = 0;
	int checker = 0;

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (checker == 0) {
				if (board[y + i][x + j] == 'B') { 
					sumw++;
				}
				else sumb++;
			}
			else {
				if (board[y + i][x + j] == 'W') { 
					sumw++; 
				}
				else sumb++;
			}
			checker++;
			checker %= 2;
		}
		checker++;
		checker %= 2;
	}

	sum = min(sumw, sumb);
	result = min(sum, result);
}

int main() {

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			search(i, j);
		}
	}

	cout << result;
}