[Algorithm] 1일1솔 - 백준 1018 체스판 다시 칠하기 (python3)

문제링크

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

1018번: 체스판 다시 칠하기

 

문제설명

[아이디어1]

N x M 판을 전체 경우의 수로 돌려야 한다. 그러기 위해서는 인덱스가 8을 넘지 않도록 조정을 해줘야 한다.

9x9에서 움직여서 조사할 수 있는 경우의 수는 2x2 = 4개이며,

10x10에서 움직여서 조사할 수 있는 경우의 수는 3x3 = 9개이고,

11x11에서 움직여서 조사할 수 있는 경우의 수는 4x4 = 16개이다.

따라서 i는 N-7의 범위에서, j는 M-7의 범위에서 움직인다.

이후에 전체 경우의 수를 다 돌면서 [아이디어2] 처럼 W로 시작한 경우, B로 시작한 경우를 나눠서 판단한다.

 

[아이디어2]

(k+l) % 2 == 0을 사용해서 행과 열의 인덱스의 합이 짝수인 경우, 일정한 한 색을 갖게 되고, 홀수인 경우에도 다른 일정한 한 색을 갖게 한다.

 

 

문제풀이

N, M = map(int, input().split())
board = [input() for _ in range(N)]
repair = []
for i in range(N-7):
    for j in range(M-7):
        first_W, first_B = 0,0
        for k in range(i, i+8):
            for l in range(j,j + 8):
                if (k + l) % 2 == 0:
                    if board[k][l] != 'W':
                        first_W += 1
                    else:  
                        first_B += 1
                else:
                    if board[k][l] != 'B':
                        first_W += 1
                    else:  
                        first_B += 1
        repair.append(first_W)
        repair.append(first_B)
print(min(repair))