백준 체크판 다시 칠하기 파이썬

문제

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

문제 요약

8 X 8 체스판으로 잘라낸 후, 정사각형을 다시 칠한다.

잘라낸 체스판마다 다시 칠하는 정사각형 개수들 중 최솟값을 구한다.

 

입력

체스판 n, m ( 8 < n, m ≤ 50 )

체스 색깔 n줄

 

출력

다시 칠하는 정사각형 최소 개수

문제 아이디어

체스판 넘어가지 않을 때까지 반복

행:  1~ 8 번째 칸 ... n-7 ~ n

열:  1~ 8 번째 칸 ... n-7 ~ n

 

i) 첫 칸 검정

ii) 첫 칸 흰색

 

두 경우 모두 다 해보고 작은 개수 cnt 구하기

cnt 값들 중 최솟값 구하기

코드

import sys

n, m = map(int, sys.stdin.readline().split())
chess = [] # 체스판 색깔
cnt = [] # 8x8 영역별 다시 칠하는 개수 최소값

for _ in range(n):
    chess.append(list(sys.stdin.readline().rstrip()))

for row in range(n-7): # n- 7 + 8 -> n-1 체스판 벗어나지 않도록
    for col in range(m-7):

        cnt1, cnt2 = 0, 0 # 각각 시작 검, 흰일때 다시 칠하는 개수
        for i in range(row, row+8):
            for j in range(col, col+8):
                if (i+j) % 2 == 0:
                    if chess[i][j] == 'B': # 시작 검은색
                        cnt1+=1
                    if chess[i][j] == 'W':
                        cnt2 += 1
                else:
                    if chess[i][j] == 'W': # 시작 흰색
                        cnt1+=1
                    if chess[i][j] == 'B':
                        cnt2 +=1
        cnt.append(min(cnt1, cnt2))  # 8x8 체스판 다시 칠하는 정사각형 최소 개수

print(min(cnt))