[BOJ/Step11] 1018 : 체스판 다시 칠하기 (Python)

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

---

 

체스판은 맨 왼쪽 위 칸이 위쪽이 검정색인 경우, 흰색인 경우 두가지가 존재한다.

 

체스판의 크기가 8*8보다 클 경우 체스판을 잘라 8*8 크기로 만들어야 하는데, 자른 후 체스판처럼 색을 칠할 때 가장 적게 정사각형을 칠하는 횟수를 구해야 한다.

 

가장 적게 정사각형을 칠하려면 어느 부분을 잘라야 하는지 알 수 없기 때문에, (0, 0) 위치를 기준으로 자를 수 있는 모든 경우의 수를 확인해 가장 적은 횟수를 구한다.

 

def re_bboard(mboard, x, y)

보드와 검사할 (x, y)좌표를 전달하면 시작이 검정색인 보드와 비교하여 다시 칠해야 할 개수를 반환

 

def re_wboard(mboard, x, y)

보드와 검사할 (x, y)좌표를 전달하면 시작이 흰색인 보드와 비교하여 다시 칠해야 할 개수를 반환

 

 

1. 입력받은 n크기의 myboard 리스트를 만들어 보드의 상태를 저장

2. 이중루프를 통해 보드를 자를 왼쪽 위 꼭지점 좌표를 (0, 0) 부터 re_bboard()와 re_wboard()를 호출하고 반환값을 mincnt 리스트에 저장

3.mincnt의 최솟값을 출력

# 1018.py

def re_bboard(mboard, x, y):
    cnt = 0
    board = ['BWBWBWBW', 'WBWBWBWB'] * 4
    for i in range(8):
        for j in range(8):
            if mboard[x + i][y + j] != board[i][j]:
                cnt += 1
    return cnt


def re_wboard(mboard, x, y):
    cnt = 0
    board = ['WBWBWBWB', 'BWBWBWBW'] * 4
    for i in range(8):
        for j in range(8):
            if mboard[x + i][y + j] != board[i][j]:
                cnt += 1
    return cnt


n, m = map(int, input().split())
myboard = [input() for _ in range(n)]
mincnt = []

for i in range(n - 7):
    for j in range(m - 7):
        mincnt.append(re_wboard(myboard, i, j))
        mincnt.append(re_bboard(myboard, i, j))

print(min(mincnt))