백준 1018번. 체스판 다시 칠하기 (Python / 파이썬)

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

---

문제 풀이

MxN 크기의 보드를 8x8로 자른 뒤

자른 보드 안에서 탐색을 진행해야 하므로

4중 for문을 이용하여 8x8로 자를 수 있는 범위를 구해주고

범위 내에서 자른 8x8 보드 안에서 탐색을 진행해주었습니다.

 

문제에서 제시된 것과 같이 체스판을 색칠하는 경우는 두 가지 입니다.

1. 맨 왼쪽 위칸이 흰색인 경우

2. 맨 왼쪽 위칸이 검은색인 경우

(0, 0)	(0, 1)	(0, 2)	(0, 3)
(1, 0)	(1, 1)	(1, 2)	(1, 3)
(2, 0)	(2, 1)	(2, 2)	(2, 3)
(3, 0)	(3, 1)	(3, 2)	(3, 3)

보드의 (i, j) 값

B	W	B	W
W	B	W	B
B	W	B	W
W	B	W	B

다음은 맨 왼쪽 위칸이 검은색인 경우 입니다. 

B의 위치와 W의 위치를 보면 

B는 i와 j의 합이 짝수 일 경우에 위치한다는 것을 알 수 있고

W는 i와 j의 합이 홀수 일 경우에 위치한다는 것을 알 수 있습니다.

맨 왼쪽 위칸이 흰색인 경우는 반대가 됩니다.

이를 통해 i와 j의 합이 짝수인 곳에는 무조건 B가 있어야 하고

홀수인 곳에는 무조건 W가 있어야 하므로

만약 각각 B와 W가 없을 시 변경 횟수를 증가시켜주면 됩니다.

 

따라서 이러한 점을 이용해 8x8 보드를 탐색하면서 

i와 j의 합이 짝수 일 경우에는

만약 B가 아니라면 2번 경우의 변경횟수를 count해주었고

W가 아니라면 1번 경우의 변경횟수를 count 해주었습니다.

i와 j의 합이 홀수 일 경우에는

만약 B가 아니라면 1번 경우의 변경횟수를 count해주었고

W가 아니라면 2번 경우의 변경횟수를 count 해주었습니다.

 

각 경우에서 count한 변경 횟수의 최솟값을 구하고 

이를 구할 수 있는 각 8x8 보드마다 구해

그 중 최솟값을 구하면 다시 칠해야 하는 개수의 최솟값을 알 수 있습니다.

---

My Code

n, m = map(int,input().split()) # 보드의 세로, 가로 크기

board = []
for _ in range(n):
  board.append(list(input())) # 보드의 상태 정보

result = 1e9
for a in range(n - 7):    # 8x8보드의 시작이 될 수 있는 범위
  for b in range(m - 7):
    count_B = 0 # 체스판이 검은색으로 시작할 경우
    count_W = 0 # 체스판이 흰색으로 시작할 경우
    for i in range(a, a + 8):
      for j in range(b, b + 8):
        if (i + j) % 2 == 0: # 가로 세로 인덱스 합이 짝수이면
          if board[i][j] != 'B': # B가 아니면
            count_B += 1         # 검은색 경우 횟수 count
          elif board[i][j] != 'W': # W가 아니면
            count_W += 1           # 흰색 경우 횟수 count
        else: # 가로 세로 인덱스 합이 홀수이면
          if board[i][j] != 'B': # B가 아니면
            count_W += 1         # 흰색 경우 횟수 count
          elif board[i][j] != 'W': # W가 아니면
            count_B += 1           # 검은색 경우 횟수 count
    min_value = min(count_B, count_W) # 최솟값
    result = min(result, min_value)   # 구할 수 있는 8x8보드 중 최솟값

print(result)