[BOJ] 1018번 체스판 다시 칠하기 (Python)

문제

해결방법

문제에 '체스판을 색칠하는 경우는 두 가지뿐이다' 라는 말로 힌트를 얻었다.
8x8 체스판은 'BWBWBWBW' 로 시작하거나 'WBWBWBWB'로 시작하는 두 가지 케이스가 있다.

패턴 형식의 배열 문제는 2로 나눈 나머지를 이용해 푸는 방식을 사용했던 기억이 있어,
같은 방식으로 접근하였다.

완전 탐색을 사용하여 8x8배열을 옮겨가면서 최소 값을 찾았다.

실제구현

시작점이 바뀔 때 마다 count_b, count_w 로 나누어서 계산 후 최소 값을 계산하였다.

import sys

n, m = map(int, sys.stdin.readline().split())
boards = [input() for _ in range(n)]
result = 64

for start_i in range(n-7):
    for start_j in range(m-7):
        count_b = 0
        count_w = 0
        for i in range(start_i, start_i+8):
            for j in range(start_j, start_j+8):
                if (i+j)%2 == 0:
                    if boards[i][j] != 'B':
                        count_b += 1
                    if boards[i][j] != 'W':
                        count_w += 1
                else:
                    if boards[i][j] != 'W':
                        count_b += 1
                    if boards[i][j] != 'B':
                        count_w += 1

        result = min(result, count_b, count_w)

print(result)

시간복잡도는 O(n*m*8*8) 이 나온다.