1018. 체스판 다시 칠하기

1. 처음 생각한 방법

- 검은색으로 시작할지 흰색으로 시작할지 알 수 없으니 두 개의 샘플은 만들어놓고 각 경우의 새로 칠하는 횟수를 비교하여 더 적은 횟수인 경우를 남긴다.

import sys
input = sys.stdin.readline

lines1 = ["WBWBWBWB", "BWBWBWBW"]
lines2 = ["BWBWBWBW", "WBWBWBWB"]

def calc_paint(r_start, c_start, tiles) :
    count_1 = 0
    count_2 = 0
    for i in range(r_start, r_start+8, 1) :
        for j in range(c_start, c_start+8, 1) :
            if tiles[i][j] != lines1[(i%8)%2][j%8] :
                count_1 += 1
            elif tiles[i][j] != lines2[(i%8)%2][j%8] :
                count_2 += 1
    return min(count_1, count_2)

cnt_min = 64
n, m = map(int, input().split())
tiles = [input().rstrip() for i in range(n)]

for i in range(0, n-7) :
    for j in range(0, m-7) :
        temp_min = calc_paint(i, j, tiles)
        if temp_min < cnt_min :
            cnt_min = temp_min

print(cnt_min)

이렇게 lines1과 lines2의 샘플은 만들어 놓고 이 샘플과 비교하여 횟수를 계산한 후, 두 경우의 횟수 중 더 작은 걸 리턴했다. 

 

그리고 다른 방법은 이렇다.

2. 다른 방법

처음 시작하는 칸이 검은색인 경우에는 (i+j)%2인 칸이 검은색이어야 한다. 따라서 처음엔 첫 칸이 검은색일 거라고 가정하고 (i+j)%2가 0이고 검은색인지, 혹은 (i+j)%2가 0이 아니고 흰색인지를 보고 아니라면 새로 칠하는 횟수를 증가시킨다.

증가시킨 결과가 32보다 크면 첫 칸이 흰색일 때(64에서 결과를 뺀 값)의 새로 칠하는 횟수가 더 적다는 이야기이다.

따라서 횟수가 32보다 크면 64-횟수를 리턴하고, 그게 아니라면 처음 계산한(첫 칸이 검정색인) 경우의 횟수를 리턴한다.

import sys
input = sys.stdin.readline

def get_count(row, col, tiles) :
    cnt = 0
    for i in range(8) :
        for j in range(8) :
            if (i+j)%2 == 0 and tiles[row+i][col+j] != 'B' :
                cnt += 1
            elif (i+j)%2 != 0 and tiles[row+i][col+j] != 'W' :
                cnt += 1
    if cnt > 32 :
        return 64-cnt
    return cnt


n, m = map(int, input().split())
tiles = [input().rstrip() for _ in range(n)]

min_count = 64

for i in range(n-8+1) :
    for j in range(m-8+1) :
        min_count = min(min_count, get_count(i, j, tiles))

print(min_count)