백준 1018 Python / 체스판 다시 칠하기 / 실버4

안녕하세요.

백준 1018 체스판 다시 칠하기 문제를 파이썬으로 풀어보겠습니다.

링크는 다음과 같습니다.

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

1018번: 체스판 다시 칠하기

 

---

풀이

 

바꿔야 하는 갯수가 가장 적은 8x8 칸을 찾는 문제입니다.

처음 생각하면 막막하지만, 천천히 생각하면 어렵지 않습니다.

반복문을 써서, 8x8 을 일단 전부 검사합니다. 0 부터 N-7 까지, 0 부터 M-7 까지면 되겠죠?

 

시작점을 정하면, 거기로부터 8 x 8 칸 중에서 색칠을 해야하는 칸을 세면 될 것입니다.

첫 째칸이 흰색이라고 하면,

흰 검 흰 검 흰 검 흰 검

검 흰 검 흰 검 흰 검 흰

...

 이런 식으로 되어야 하는데, 보면 (행, 열) 에서 행과 열을 합친 값이 짝수면 첫 번째 값과 같다, 홀수면 달라야 한다는 점을 알 수 있습니다.

따라서, 행 + 열 값이 짝수일 때, 첫 번째칸과 다르면 칠해야 하고, 홀수일 때는 같으면 칠해야 합니다.

 

마지막으로, 8x8 = 64 칸의 체스판에서 32칸을 넘게 칠해야 하는 경우면 첫 번째 칸의 기준점을 뒤엎는 것이 더 적게 칠하게 될 것입니다.

따라서, 32칸을 넘는 경우엔 64칸에서 칠할 갯수 만큼을 뺀 것이 칠할 칸 갯수가 되겠습니다.

 

코드로 보면 다음과 같습니다.

 

import sys

def count_paint(m, y, x):
    count = 0 # 페인트 칠할 갯수
    base = board[y][x] # 첫 번째 칸
    for i in range(y, y+8): # 8x8 검사
        for j in range(x, x+8):
            if (i+j) % 2 == 0: # --> 첫 번째 칸과 같아야 하는 칸
                if board[i][j] != base:
                    count += 1
            else: # --> 첫 번째 칸과 달라야 하는 칸
                if board[i][j] == base:
                    count += 1
    if count > 32:
        count = 64 - count # 기준 바꾸기(첫 번째 칸 색 반전)
    return count if m > count else m # 최솟값 갱신

N, M = map(int, sys.stdin.readline().split())
board = []
answer = 32
for _ in range(N):
    board.append(list(sys.stdin.readline().strip()))

for i in range(N - 7): # 8x8 시작점 찾기
    for j in range(M - 7):
        answer = count_paint(answer, i, j) # 페인트칠 최솟값 찾기

print(answer)

 

감사합니다.