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

문제

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

1018번: 체스판 다시 칠하기

---

문제 요약

M × N 크기의 보드를 잘라서 8 × 8 크기의 체스판으로 만들어야한다.

 

체스판은 2가지 종류가 있다.

1. 맨 왼쪽 위 칸이 흰색인 경우

2. 맨 왼쪽 위 칸이 검은색인 경우

 

M × N 크기의 보드에서  8 × 8 크기를 아무데나 골라서 체스판을 만들 때, 칠해야 하는 정사각형의 최소 개수를 출력한다.

---

코드

def w_count(i, j): # 맨 왼쪽 위 칸(i, j)이 흰 체스판으로 칠할 때 정사각형 개수
    cnt = 0
    for x in range(8):
        for y in range(8):
            if arr[i + x][j + y] != w_board[x][y]:
                cnt += 1
    return cnt

def b_count(i, j): # 맨 왼쪽 위 칸(i, j)이 검은 체스판으로 칠할 때 정사각형 개수
    cnt = 0
    for x in range(8):
        for y in range(8):
            if arr[i + x][j + y] != b_board[x][y]:
                cnt += 1
    return cnt

N, M = map(int, input().split())
# N은 세로 길이, M은 가로 길이

arr = [list(input()) for _ in range(N)]

"""for line in arr:
    print(*line)"""

w_board = [['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'], ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'], ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'], ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'], ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'], ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'], ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'], ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']]
b_board = [['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'], ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'], ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'], ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'], ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'], ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'], ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'], ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B']]

""" for board in w_board:
    print(*board)

print()

for board in b_board:
    print(*board) """

res = 64

# 맨 왼쪽 위 칸이 가능한 인덱스들 접근
for i in range(0, N - 7):
    for j in range(0, M - 7):
        res = min(res, w_count(i, j), b_count(i, j))

print(res)

---

코드 설명

1. 미리 맨 위쪽 칸이 검은 체스판과 흰 체스판을 2차원 배열로 생성한다.

 

2. 맨 왼쪽 위 칸이 가능한 인덱스들을 이중 반복문으로 접근하고 w_count, b_count 함수를 이용하여 두 체스판으로 칠할 때 필요한 개수를 구하고 최소 값으로 갱신한다.

+ 맨 왼쪽 위 칸이 검은색, 흰색이 모두 가능하므로 두 함수 모두 호출하여 비교한다.

 

3. 최소 개수를 출력한다.