[백준 1018] 체스판 칠하기 (C++/Python)

1. 입력

- m 가로 n 세로

- b 검은색 w 흰색

2. 출력

- 다시 칠해야 하는 정사각형 개수의 최소값

3. 조건

- 체스판은 대각선끼리 색깔 같음

4. 시간복잡도

- 체스판이 최대 50x50이므로 8x8으로 잘라서 검사한다면 42*42 케이스가 있음

- 잘라낸 체스판 색깔 검사를 하는데 흰색 검은색 -> 8*8*2

- 총 시간복잡도 (42*42)*(8*8*2) 

 

5. 풀이

- 예를 들어, 체스판 시작 (왼쪽 제일 상단)이 흰색이라 하더라도 검정색으로 시작했을 때 정사각형을 더 적게 색칠할 수 있는 경우가 있기 때문에 체스판 시작을 W,B 두가지 색 전부 테스트해야한다.

 

---

 

C++)

#include <iostream>
#include <algorithm>
#define MAX_NUM 52

using namespace std;

string arr[MAX_NUM];

int GetAnswer(int x, int y) {
	char colors[2] = { 'W', 'B' };
	int returnValue = 987654321;

	for (int cnt = 0; cnt < 2; cnt++) {
		char color = colors[cnt];
		int count = 0;

		for (int i = x; i < x + 8; i++) {
			for (int j = y; j < y + 8; j++) {
            	// 체스판 시작과 대각선이고 -> 색깔이 같아야함
                // 근데 색깔이 달라서 다시 칠해야함
				if (((i + j) % 2 == (x + y) % 2) && arr[i][j] != color) 
					count++;
                    
                // 체스판 시작과 대각선이 아니고 -> 색깔이 같아야함
                // 근데 색깔이 같아서 다시 칠해야함
				else if (((i + j) % 2 != (x + y) % 2) && arr[i][j] == color) 
					count++;
			}
		}

		returnValue = min(count, returnValue);
	}

	return returnValue;
}

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

	int m, n;
	cin >> n >> m;

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

	int ans = 987654321;

	for (int i = 0; i <= n - 8; i++) {
		for (int j = 0; j <= m - 8; j++) {
			ans = min(ans, GetAnswer(i, j));
		}
	}

	cout << ans;

	return 0;
}

 

 

 

Python)

import sys

read = sys.stdin.readline

n, m = map(int, read().rstrip().split())
arr = [read().rstrip() for _ in range(n)]
ans = 987654321

def get_answer(x, y):
    colors = ['W', 'B']
    return_value = 987654321

    for color in colors:
        cnt = 0

        for i in range(x, x+8):
            for j in range(y, y+8):
                if (i+j)%2 == (x+y)%2 and arr[i][j] != color:
                    cnt += 1
                elif (i+j)%2 != (x+y)%2 and arr[i][j] == color:
                    cnt += 1

        return_value = min(return_value, cnt)
    
    return return_value

for i in range(n-8+1):
    for j in range(m-8+1):
        ans = min(ans, get_answer(i,j))

print(ans)

 

 

라고 풀었는데 W,B 둘다 검사할 필요 없이 체스판 90도 회전시키면 흑백 반전되기 때문에 min(count, 64-count)가 최소 수정횟수이다..^^

역시 사람은 똑똑해야한다...

int GetAnswer(int x, int y) {
	int count = 0;

	for (int i = x; i < x + 8; i++) {
		for (int j = y; j < y + 8; j++) {
			if (((i + j) % 2 == (x + y) % 2) && arr[i][j] != arr[x][y])
				count++;
			else if (((i + j) % 2 != (x + y) % 2) && arr[i][j] == arr[x][y])
				count++;
		}
	}

	return min(count, 64-count);
}