[BOJ] 1018. 체스판 다시 칠하기(python)

📌문제

💪아이디어

1. 보드판 사이즈 조절
   
   • 가로 0 ~ m-8 / 세로 0 ~ n-8 까지 왼쪽 아래쪽으로 움직이며 8X8 보드판 사이즈 잡기
2. 시작점 돌색
   
   • 검은색 : 상하좌우 흰색돌이어야함
     
   • 하얀색 : 상하좌우 흰색돌이어야함
     
3. 보드 검사
   
   • 시작점 돌색을 2가지 경우로 나누어 bfs로 보드판 돌색 검사
     
   • 검사결과와 보드판에 색칠된 돌색이 다르면 cnt로 수를 셈
     

     🥂코드

from collections import deque

dy = (1,0,-1,0)
dx = (0,1,0,-1)

def board_chk(y,x,color):
    chk = [[False for _ in range(m)]for _ in range(n)]
    queue=deque()
    queue.append((y,x,color))
    chk[y][x]=True

    if board[y][x]==color: cnt=0
    else: cnt=1

    while queue:
        nxt_y,nxt_x,nxt_c = queue.popleft()
        for i in range(4):
            ny,nx = nxt_y + dy[i], nxt_x + dx[i]
            if y<=ny<y+8 and x<=nx<x+8:
                if not chk[ny][nx]:
                    chk[ny][nx]=True
                    if nxt_c=='B': c='W'
                    else: c='B'
                    if board[ny][nx]!=c: cnt+=1
                    queue.append((ny,nx,c))
    return cnt

n,m = map(int,input().split()) #세로, 가로
board=[]
for _ in range(n):
    board.append(input())

answer=float('inf')
for i in range(n-7):
    for j in range(m-7):
        cnt1 = board_chk(i,j,'B')
        cnt2 = board_chk(i,j,'W')
        answer=min(answer,cnt1,cnt2)
print(answer)