백준 알고리즘 1018 (체스판 다시 칠하기) - C++, Python

[문제] 백준 알고리즘 1018 (체스판 다시 칠하기)

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

1018번: 체스판 다시 칠하기

 

M * N의 보드에 "B" 또는 "W"가 적혀있다. 8 * 8 크기로 아무 곳이나 잘라서 체스판을 만들면 된다.

이 중에, 가장 적게 "B" 또는 "W"를 교체하도록 8 * 8을 자르고, 그 교체 수를 찾는 문제이다.

주의할 점은 체스판은 BWBW.... 경우와 WBWB.... 경우의 두 가지가 있다.

 

for문에서 i + j번째의 짝수 vs 홀수 검사, 이 때의 보드[i][j] 값의 "B" vs "W" 검사를 한다.

쉽게 생각하면, 맨 처음이 "B"인 경우는 BWBW.... 의 체스판을 가정한 것이다.

이 때, i + j = 0으로 i + j가 짝수일 때 "B"이고, i +j가 홀수일 때는 "W"이다. 

따라서, i + j가 짝수일 때 "B"이면 cntBW를 카운트하고, 반대일 때는 cntWB를 카운트했다.

 

[C++]

#include <iostream>
#include <algorithm>
using namespace std;

char B[51][51];

int block_cnt(int _i, int _j) {
	int cntWB = 0;
	int cntBW = 0;
	for (int i2 = _i; i2 < _i + 8; i2++) {
		for (int j2 = _j; j2 < _j + 8; j2++) {
			if ((i2 - _i + j2 - _j) % 2 == 0) {
				if (B[i2][j2] == 'B') cntWB++;
				else cntBW++;
			}
			else {
				if (B[i2][j2] == 'W') cntWB++;
				else cntBW++;
			}
		}
	}
	return min(cntWB, cntBW);
}

int main() {
	int n, m;
	cin >> n >> m;

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

	int _min = n * m;
	for (int i = 0; i < n - 7; i++) {
		for (int j = 0; j < m - 7; j++) {
			int cnt = 0;
			cnt = block_cnt(i, j);
			_min = min(_min, cnt);
		}
	}
	cout << _min << endl;
	return 0;
}

 

[Python]

import sys
N, M = map(int, input().split())
B = [list(sys.stdin.readline().rstrip()) for _ in range(N)]

def block_cnt(_i, _j):
    cntWB = 0
    cntBW = 0
    for i2 in range(_i, _i+8):
        for j2 in range(_j, _j+8):
            if (i2 - _i + j2 - _j) % 2 == 0:
                if B[i2][j2] == 'B':
                    cntWB += 1
                else:
                    cntBW += 1
            else:
                if B[i2][j2] == 'W':
                    cntWB += 1
                else:
                    cntBW += 1
    return cntWB, cntBW

_min = N * M
for i in range(N-7):
    for j in range(M-7):
        cnt1, cnt2 = block_cnt(i, j)
        _min = min(_min, cnt1, cnt2)
print(_min)