[백준] 1018: 체스판 다시 칠하기 - 파이썬[python]

문제는 이해했지만 놓친 포인트가 있어서 제대로 된 코드를 짜는 데 애먹었다..

코드

N, M = map(int, input().split())
board = []
result = 64

for i in range(N):
    board.append(list(input()))

for i in range(N-7):
    for j in range(M-7):
        countW = 0 # 좌상단이 W인 경우
        countB = 0 # 좌상단이 B인 경우
        for a in range(i, i+8):
            for b in range(j, j+8):
                if (a + b) % 2 == 0:
                    if board[a][b] != 'W':
                        countW += 1
                    if board[a][b] != 'B':
                        countB += 1
                else:
                    if board[a][b] == 'W':
                        countW += 1
                    if board[a][b] == 'B':
                        countB += 1
        result = min(result, countW, countB)

print(result)

풀이

1. 먼저 입력받는 각 줄을 리스트로 바꿔주고 저장한다.
2. 가능한 8*8 체스판을 모두 검사하기 위해 i와 j를 나눠 for문을 돌린다.
3. 이제 만들어진 8*8 체스판에서 모든 칸을 검사해서 다시 칠해야 하는 최소 개수를 구한다.
4. 지그재그(?)로 흰/검이 바뀌므로 (a + b) % 2를 활용하여 체스판을 두 가지 경우의 수로 나눈다.
5. 좌상단이 흰색으로 시작할 경우와 검정으로 시작할 경우가 존재하므로 두 가지 경우를 나누어서 칠할 개수를 구한다.
6. 기존의 result, 좌상단이 흰색일 경우, 좌상단이 검정이 경우에 세었던 개수 중 가장 작은 수를 result로 갱신한다.

나의 실수

1. 나는 처음에 좌상단이 흰/검인 경우를 나누지 않았다. 만들어진 8*8 체스판에서 좌상단에 처음부터 칠해진 색깔을 따르면 된다고 생각해버렸다. 그런데, 처음에 칠해진 색깔이 검정이더라도 흰색으로 바꾸면 더 적은 칸을 칠할 수도 있기에 두 가지 경우를 나눠서 카운트해야 한다.
2. (a + b) % 2 == 0를 쓰지 않고

if (i%2 == a%2 and j%2 == b%2) or (i%2 != a%2 and j%2 != b%2):

막 이런 식으로 했었다..
저렇게 간단한 방법이 있었다니..

결론

이번 문제는 좀 많이 어려웠다. 브루트 포스 문제답게 경우의 수를 다 따져서 코드를 짜야 했다. 다음엔 꼭 내 힘으로 완벽히 해보자..