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

1018번: 체스판 다시 칠하기

# 8 <= n, m <= 50
n, m = map(int,input().split())

board = [list(input()) for _ in range(n)]

white_board = [['']*8 for _ in range(8)]
black_board = [['']*8 for _ in range(8)]

start_with_white = True

min_value = float("inf")

for i in range(8):
    for j in range(8):
        if start_with_white:
            white_board[i][j] = "W"
            black_board[i][j] = "B"
        else:
            white_board[i][j] = "B"
            black_board[i][j] = "W"
        if j != 7:
            start_with_white = not start_with_white

def calculate_diff_with_white(arr):
    diff = 0
    for i in range(8):
        for j in range(8):
            if arr[i][j] != white_board[i][j]:
                diff += 1
    
    return diff

def calculate_diff_with_black(arr):
    diff = 0
    for i in range(8):
        for j in range(8):
            if arr[i][j] != black_board[i][j]:
                diff += 1
    
    return diff

for i in range(n):
    for j in range(m):
        if (i + 7) < n and (j + 7) < m:
            temp_board = []
            for k in range(8):
                temp_board.append(board[i+k][j:j+8])
            min_value = min(calculate_diff_with_black(temp_board),calculate_diff_with_white(temp_board),min_value)

print(min_value)

이번 문제는 M x N크기의 보드에서 8x8 크기의 보드를 임의로 잘라냈을 때, 다시 칠해야 하는 영역의 개수의 최소값을 구하는 문제이다.

 

먼저 좌측 상단이 흰색으로 시작하는 보드와, 검은색으로 시작하는 보드 2개를 먼저 선언한 뒤에 다시 칠해야 하는 영역(차이나는 영역)의 개수를 구하는 함수를 선언하였다. 그 후 모든 8x8 크기의 경우의 수를 모두 비교해가며 최솟값을 갱신해주었다.

 

완전탐색을 연습해볼 수 있었던 좋은 문제였다 :)