백준-1018-체스판 다시 칠하기

문제 링크: https://www.acmicpc.net/problem/1018

코드

코드1

def get_paint_count(start_row_idx, start_col_idx):
    count1 = 0
    count2 = 0
    for i in range(start_row_idx, start_row_idx + 8):
        for j in range(start_col_idx, start_col_idx + 8):
            if input_board[i][j] != sample_board1[i][j]:
                count1 += 1
            if input_board[i][j] != sample_board2[i][j]:
                count2 += 1
                
    return min(count1, count2)
    
n, m = map(int, input().split())
input_board = []
for _ in range(n):
    input_board.append(list(input()))

sample_board1 = [['B' if (i+j)%2 == 0 else 'W' for j in range(m)] for i in range(n)]
sample_board2 = [['W' if (i+j)%2 == 0 else 'B' for j in range(m)] for i in range(n)]

min_count = 64

for i in range(n-7):
    for j in range(m-7):
        min_count = min(min_count, get_paint_count(i, j))
        
print(min_count)

코드2

def get_paint_count(board, start_row_idx, start_col_idx):
    count1 = 0
    count2 = 0
    for i in range(start_row_idx, start_row_idx + 8):
        for j in range(start_col_idx, start_col_idx + 8):
            if (i + j) % 2 == 0:
                count1 += 0 if board[i][j] == 'B' else 1
                count2 += 1 if board[i][j] == 'B' else 0
            else:
                count1 += 1 if board[i][j] == 'B' else 0
                count2 += 0 if board[i][j] == 'B' else 1
                
    return min(count1, count2)
    
n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(input()))

min_count = 64

for i in range(n-7):
    for j in range(m-7):
        min_count = min(min_count, get_paint_count(board, i, j))
        
print(min_count)

풀이

문제의 조건에도 나와 있듯, 올바르게 된 체스판은 두 종류로 구분할 수 있다. 좌상단이 까만색('B')인 체스판과 흰색('W')인 체스판.

따라서 MxN 크기의 체스판을 임의로 8x8 부분 체스판들로 나눴다고 했을 때 각 체스판을 '좌상단이 까만색인 샘플 체스판'과 '좌상단이 흰색인 샘플 체스판'과 비교하여 바꿔줘야 하는 블록의 개수를 얻어 그 중 더 작은 값을 해당 부분 체스판의 결과값으로 할당한다.

부분 체스판들의 결과값 중 최솟값을 return하면 그것이 MxN 크기의 체스판을 임의의 8x8 체스판으로 나누었을 때 바꿔줘야 할 체스 블록의 최솟값이 된다.

근거

8<=N, M<=50이다. 따라서 N, M이 최대일 경우에 나올 수 있는 부분 체스판의 개수는 43*43개이고 각 부분 체스판의 경우에 총 64번의 비교 연산을 수행하므로 brute-force로 풀어도 충분히 시간 제한을 맞출 수 있다.