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

📌문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

📌풀이

4중 for문 사용

첫번째 두번째 for문은 전체 체스판에서 시작점을 잡기 위한 용도

해당 지점부터 8x8 크기의 체스판을 만들었을 때 전체 보드판의 범위를 넘어가면 안되니까 -7

 

행과 열의 시작점 i,j를 기준으로 8칸씩 모두 검사

현재 행의 번호 a, 현재 열의 번호 b의 합이 짝수이면 시작점의 색깔과 같아야 하고,

홀수이면 시작점의 색깔과 다른 색이어야 함

 

a,b의 합이 짝수인 경우(시작점의 색깔과 같아야 함)

draw1에서는 B로 시작하는 체스판이므로 B가 아닐 경우 다시 색칠해야 하니까 draw1+=1

draw2에서는 W로 시작하는 체스판이므로 W가 아닐 경우 다시 색칠해야 하니까 draw2+=1

 

a,b의 합이 홀수인 경우(시작점의 색깔과 달라야 함)

draw1에서는 B로 시작하는 체스판이므로 B와 다른 W여야 하는데 W가 아닐 경우 다시 색칠해야 하니까 draw1+=1

draw2에서는 W로 시작하는 체스판이므로 W와 다른 B여야 하는데 B가 아닐 경우 다시 색칠해야 하니까 draw2+=1

 

B로 시작하는 체스판(draw1), W로 시작하는 체스판(draw2) 중 다시 칠해야하는 정사각형의 수가 작은 것 출력

 

📌코드

n, m = map(int, input().split())
board = []
result = []

for _ in range(n):
    board.append(input())

# 이 지점부터 8x8 크기의 체스판 검사 시 전체 보드판 범위를 넘어가지 않기 위해 -7
for i in range(n - 7):
    for j in range(m - 7):
        draw1 = 0  # B로 시작하는 체스판을 만들때 다시 칠해야 하는 칸 수
        draw2 = 0  # W로 시작하는 체스판을 만들때 다시 칠해야 하는 칸 수
        for a in range(i, i + 8):
            for b in range(j, j + 8):
                if (a + b) % 2 == 0:
                    if board[a][b] != "B":
                        draw1 += 1
                    if board[a][b] != "W":
                        draw2 += 1
                else:
                    if board[a][b] != "W":
                        draw1 += 1
                    if board[a][b] != "B":
                        draw2 += 1
        result.append(draw1)
        result.append(draw2)
print(min(result))