[백준/Python] 1018번 체스판 다시 칠하기 문제

■ 1018번 체스판 다시 칠하기 문제

 

출처: 백준 1018번 체스판 다시 칠하기 문제

 

■ 코드 풀이

 

개인적으로 너무 어려웠던 문제였습니다. 다른 분의 코드를 참고하여 문제를 풀었습니다. 핵심 아이디어는 Convolution 연산과 비슷합니다. 크기가 큰 이미지가 있으면, 8 by 8 짜리 작은 Window가 그 이미지를 쭉 스캔한다고 생각하시면 됩니다. 전체 이미지에서 스캔의 범위를 정하기 위해 for문이 2개(i와 j) 필요합니다.

문제에서 색깔은 'B'와 'W' 밖에 없고, 각각 번갈아서 색칠되어야 하기 때문에 제일 위의 왼쪽 Block의 색깔에 따라 2가지 경우밖에 없다고 제시했습니다. 따라서 이 두 가지 경우에 대해서만 고려하면 됩니다. 이를 위해 8 by 8 Window가 선택되었다면 그 안에서 첫 번째 Block이 'B'인 경우(is_it_black)와 'W'인 경우(is_it_white)에 대해서 또다시 for문을 2개(a와 b) 실행합니다.

첫 번째 Block이 'B'인 경우에는 바로 한 칸 옆의 Block이 'B'인 경우와 두 칸 옆의 Block이 'W'면 각각 is_it_black에 1을 더해줍니다. 첫 번째 Block이 'W'인 경우는 정확히 그 반대입니다. 따라서 아래 코드를 실행하게 된다면, 8 by 8 Window가 주어진 전체 보드를 스캔하면서 Window 안에서 2가지 경우의 수에 대해 각각 색깔을 몇 번 바꿔야 하는지 '모든 경우의 수'를 result라는 list에 기록합니다. 그리고 이 list에 최솟값을 출력하면 그게 바로 정답입니다.

 

N,M = map(int, input().split())

board = []
result = []
 
for _ in range(N):
    board.append(input())
 
for i in range(N-7):
    for j in range(M-7):
        is_it_black = 0
        is_it_white = 0
 
        for a in range(i, i+8):
            for b in range(j, j+8):
                if (a + b) % 2 == 0:
                    if board[a][b] != 'B':
                        is_it_black += 1
                    if board[a][b] != 'W':
                        is_it_white += 1
                else:
                    if board[a][b] != 'W':
                        is_it_black += 1
                    if board[a][b] != 'B':
                        is_it_white += 1
 
        result.append(is_it_black)
        result.append(is_it_white)
 
print(min(result))