2023-06-10 BOJ 1018 체스판 다시 칠하기

문제 링크

문제 풀이 방식

• 체스판 전체를 검사해야 하니까 brute force
  • 가능한 전체 시작점을 반복(반복문)
  • tmp1에 흰색으로 시작하는 체스판을 다시 칠하는 칸 수를 저장
  • tmp2에 검은색으로 시작하는 체스판을 다시 칠하는 칸 수를 저장
  • for 루프 내에서 체스판 내 8X8 영역을 확인하고, (X+Y) 값에 따라 각 변수를 증가시킨다.
    • 합이 짝수고 흰색으로 시작하는 체스판인데 해당 칸이 흰색이 아니면 다시 색칠해야 한다 (tmp1을 1 증가시킨다)
    • 합이 짝수고 검은색으로 시작하는 체스판인데 해당 칸이 검은색이 아니면 다시 색칠해야 한다 (tmp2을 1 증가시킨다)
    • 합이 홀수고 검은색으로 시작하는 체스판인데 해당 칸이 흰색이 아니면 다시 색칠해야 한다 (tmp2을 1 증가시킨다)
    • 합이 홀수고 흰색으로 시작하는 체스판인데 해당 칸이 검은색이 아니면 다시 색칠해야 한다 (tmp1을 1 증가시킨다)
  • 후보 값들을 배열에 저장하고, 저장된 값들 중 최소값을 출력한다.

문제 풀이 (Python)

import sys
r = sys.stdin.readline
N, M = map(int, r().split())

checkerboard = [r() for _ in range(N)]
checkerboardcnts = []
for i in range(N-7):
    for j in range(M-7):
        temp1 = 0
        temp2 = 0
        
        for y in range(i, i+8):
            for x in range(j, j+8):
                if (x+y)%2:
                    if checkerboard[y][x] != "W": temp1 +=1
                    if checkerboard[y][x] != "B": temp2 +=1
                else:
                    if checkerboard[y][x] != "W": temp2 +=1
                    if checkerboard[y][x] != "B": temp1 +=1
                    
        checkerboardcnts.append(min(temp1, temp2))
                    
print(min(checkerboardcnts))