[Python] 백준 1018 체스판 다시 칠하기

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

문제분석

W와 B로 주어진 판에서, 최소한으로 뒤집어서 체스판을 만들 수 있을 때 그 최소값을 구하는 문제이다.

해결과정

8*8 체스판을 구하는 것 이므로, N*M판에서 우리가 봐야 할 첫번째 칸의 위치는 (N-8)*(M-8)에 위치한다.

첫번째 체스칸의 색을 기준으로 나머지 모든 칸의 색이 정해지므로, 첫번째 색과 같은지 다른지 확인하면 될 것이라고 생각했다.

구현이 은근 어렵다. 구현해놓고 나서, 시간 초과 뜨면 접으려고 했는데 다행이 정답 떠줬다...ㅠㅠ

from sys import stdin
def input():
    return stdin.readline().rstrip()
N,M=map(int,input().split())
arr=[] # W는 1 B 는 0 으로 저장할 계획
for _ in range(N):
    templist=list(input())
    inputlist=[]
    for i in range(M):
        if templist[i]=='W':
            inputlist.append(1)
        else:# B
            inputlist.append(0)
    arr.append(inputlist)

result=float('inf')
for i in range(2):
    for j in range(N-7):
        for k in range(M-7):
            temp=0
            for p in range(8):

                for m in range(4):
                    if arr[j+p][k+m*2]==(i+p%2)%2:temp+=1
                    if arr[j+p][k+m*2+1]==(i+(p+1)%2)%2:temp+=1
            result=min(result,temp)
print(result)