백준 1018 : 체스판 다시 칠하기 (파이썬)

체스판 다시 칠하기 

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

 

---

코드

import sys
N, M = map(int,sys.stdin.readline().split())
board = [[m for m in sys.stdin.readline().rstrip()] for _ in range(N)]
case1 = [[0 for _ in range(M)] for _ in range(N)]
case2 = [[0 for _ in range(M)] for _ in range(N)]
for n in range(N):
    for m in range(M):
        if (n+m)%2 == 0:
            if board[n][m] == 'W': case2[n][m] = 1
            else: case1[n][m] = 1
        else:
            if board[n][m] == 'W': case1[n][m] = 1
            else: case2[n][m] = 1

answer = 50*50
for a in range(N-7):
    for b in range(M-7):
        white = sum([case1[i][j] for i in range(a,a+8) for j in range(b,b+8)])
        black = sum([case2[i][j] for i in range(a,a+8) for j in range(b,b+8)])
        answer = min(answer, white, black)
        if answer == 0 : break
print(answer)

해설

1. 보드와 같은 크기로 2개의 배열을 만들기

하나의 경우는 좌측상단에 하얀색을 시작으로 칠하는 경우(case1)
다른 하나의 경우는 좌측상단에 검은색을 시작으로 칠하는 경우(case 2)

2. 보드를 전부다 확인하여 case1일 때 새로 칠해야 하면 해당 자리의 case1을 1로 변경함. case 2 또한 동시에 진행

3. 만들어진 case1, case 2를 8x8로 자를 수 있는 모든 경우의 수를 확인해 가장 적게 칠하는 경우를 찾아냄.