체스판 다시 칠하기 [백준 1018](파이썬)

문제

---

체스판 다시 칠하기 [백준 1018]
https://www.acmicpc.net/problem/1018

풀이

---

티어가 실버 4이길래 그렇게 어렵지 않을 줄 알았는데 결국 못 풀고 다른 블로그 풀이를 참고하게 되어서 이 풀이를 기록에 남긴다.
큰 판이 주어지면 8 * 8 로 잘라서 색깔이 반복되는 체스판을 만드는 것이다. 내가 생각한 풀이는 이렇다.

• 숫자가 그리 크지 않으니 한칸씩 8 * 8 체스판의 시작점을 옮겨가며 새로 칠해보고 나오는 최소의 값을 반환하자.
• 자른 뒤 8 * 8 체스판을 돌며 현재 칸과 주변 상하좌우 칸이 색이 다르면 count 를 올리고 바꿔주자.

이렇게 풀면서도 아 이럼 나중에 색이 꼬이면 최소의 색칠 횟수가 나오질 않을 거 같긴 했는데 결국 그렇게 나왔다.
다른 풀이는 이렇다.

• 시작점의 색깔은 백 아님 흑이다.
• 좌표를 더한 값이 짝수면 시작점과 같은색, 홀수면 다른 색이다.
• 시작판이 흑이나 백일 때 색칠 횟수를 구하고 그 중 제일 작은 값으로 한다.

코드

---

import copy
n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
result = 64
def check(x, y):
    count1 = 0
    count2 = 0
    for i in range(8):
        for j in range(8):
            col, row = x + i, y + j
            if (col + row) % 2 == 0:        # 첫번째와 색깔 같음
                if board[col][row] == 'B':  # w로 시작
                    count1 += 1
                else:                       # b로 시작
                    count2 += 1
            else:                           # 첫번째와 색깔 다름
                if board[col][row] == 'W':  
                    count1 += 1
                else:
                    count2 += 1
    return min(count2, count1)


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