[BOJ/백준] 1018번 체스판 다시 칠하기

문제

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

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

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

---

입력

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

---

출력

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

입/출력

---

풀이

n,m = map(int,input().split())
board = list()
for _ in range(n):
  board.append(input())
repair = list()

for i in range(n-7):# 8*8로 잘라야 하기 때문에 i-7 만큼 ,j-7만큼 고정
  for j in range(m-7):
    W = 0
    B = 0
    for k in range(i,i+8):
      for l in range(j,j+8):
        if (k+l) % 2 == 0 : # 흰색이 먼저 있는 경우
          if board[k][l] != 'W':
            W += 1
          if board[k][l] != 'B':
            B += 1
        else: # 검정색이 먼저 있는 경우
          if board[k][l] != 'B':
            W += 1
          if board[k][l] != 'W':
            B += 1
    repair.append(W)
    repair.append(B)
print(min(repair))

결과

---

느낀 점

이 문제는 8x8로 자르는 것을 먼저 어떻게 풀어나갈 것인지 생각해봐야 하는 문제인 것 같다. 4중 for 문을 사용해서 문제를 해결할 수 있었는데 다른 방법으로도 충분히 풀어나갈 수 있을 것 같은 문제였다. k, l 즉 행과 열을 더하면 짝수. 홀수 상태에 특정한 규칙을 찾을 수 있다. 이 규칙을 이용해서 처음 흰색이 먼저 나오는 것과 검은색이 나오는 것을 구별해서 문제를 해결할 수 있다.