(Python) - BOJ(1018번) : 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

 

• 해설 :

White와 Black으로 이루어진 N*M 사이즈의 체스판이 주어진다. 이 체스판을 8 x 8의 사이즈로 자르려고 할 때, W와 B가 번갈아가면서 나오는 체스판의 원래 패턴을 만들어주기 위해 최소 몇 개의 칸을 칠해야 하는지 찾는 문제이다.

 

 

 

 

• 풀이 :

8 x 8로 자를 수 있는 모든 경우에 대해 이중 for문으로 전부 탐색하며 W 또는 B로 색칠해야하는 개수를 카운트해준다. 이를 min으로 최솟값 갱신하고 마지막에 정답을 도출한다.

 

 

 

 

import sys
input = sys.stdin.readline
 
def cnt(lst):
    w_cnt = 0
    b_cnt = 0
    w_cnt1 = 0
    b_cnt1 = 0
    for i in range(8):
        for j in range(8):
            if (i+j)%2 == 0:
                if lst[i][j] == 'W':
                    w_cnt += 1
                else:
                    b_cnt += 1
            else:
                if lst[i][j] == 'W':
                    w_cnt1 += 1
                else:
                    b_cnt1 += 1
    return min(64-(w_cnt+b_cnt1),64-(b_cnt+w_cnt1))
 
if __name__ == "__main__":
    N,M = map(int,input().split())
    board = [list(input().strip()) for _ in range(N)]
    ans = 64
    for i in range(N-7):
        for j in range(M-7):
            ans = min(ans,cnt([board[k][j:j+8] for k in range(i,i+8)]))
    print(ans)