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

📌 문제

💯 정답

# 1. NXM 행렬이 주어졌을 때 몇개의 8X8 체스판을 만들 수 있는지
# 2. 한 체스판 검사시 i+8개의 행과 j+8개의 열을 검사한다.
# 3. 행과 열의 합이 짝수일때의 모든 타일은 같은 색을 가져야하고
#    행과 열의 합이 홀수일때의 모든 타일은 짝수일때의 타일과는 다른 색이어야 한다.
# 4. 짝수일때 시작타일의 색이 w일때와 b일때로 나누어 체크하고
#    홀수일때 시작타일과는 다른 색인지 체크한다.
# 5. w로 시작했을 때와 b로 시작했을 때 고쳐야하는 타일수를 list에 담아 min값을 출력한다.

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

for i in range(n-7):
    for j in range(m-7):
        first_w = 0             # 첫번째 칸을 흰색으로 시작할 때
        first_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로 시작했는데 w가 아니면
                        first_w = first_w + 1
                    if board[k][l] != 'B':      # b로 시작했는데 b가 아니면
                        first_b = first_b + 1
                else:                           # (짝 홀) (홀 짝) 행렬 색 처음과 색 달라야 함
                    if board[k][l] != 'B':      # w로 시작했는데 b가 아니면
                        first_w = first_w + 1
                    if board[k][l] != 'W':      # b로 시작했는데 w가 아니면
                        first_b = first_b + 1
        repair.append(first_w)
        repair.append(first_b)

print(min(repair))

📝 설명

• board에  N X M 크기의 보드를 입력받는다.

• N X M 크기의 보드에서 8 X 8 크기의 체스판을 만드는 경우의 수는 (N-7) X (M-7) 이다.
  ex. 9 X 9 크기의 보드 -> 4가지 (2 X 2) 경우의 체스판
  	  10 X 10 크기의 보드 -> 9가지 (3 X 3) 경우의 체스판
      (아래의 그림을 참고하면 편하다.)
      
• 가능한 경우 중 하나의 체스판을 검사할때 첫칸이 W일때, B일때로 나누어 검사한다.

• 체스판에서 행+열이 짝일때와 홀일때 색은 무조건 같아야 문제의 조건을 만족한다.

• 우선 짝일경우
  첫칸(0+0으로 짝인 칸)을 W로 시작했는데 짝인 칸이 W가 아니면 first_w에 1을 더하고,
  첫칸을 B로 시작했는데 짝인 칸이 B가 아니면 first_b에 1을 더한다.
  
• 그 다음 홀일경우
  첫칸(짝인 칸)을 W로 시작했는데 홀인 칸이 B가 아니면 first_w에 1을 더하고,
  첫칸을 B로 시작했는데 홀인 칸이 W가 아니면 first_b에 1을 더한다.
  
• 이렇게 하나의 체스판을 검사할때마다
  first_w에는 첫칸을 W로 시작했을 때 고쳐야하는 칸의 수,
  first_b에는 첫칸을 b로 시작했을 때 고쳐야하는 칸의 수가 들어가게 되고
  이를 repair 리스트에 추가한다.

• 만약 처음 입력받은 board가 9 X 9였다면
  repair엔 4가지의 first_w과 4가지의 first_b가 들어있어
  총 8개의 인자가 들어있을 것이다.

• 이중 가장 고쳐야 할 칸의 수가 적은 값을 min을 이용해 출력한다.

ex. 9 X 9 크기 보드 -> 4가지 경우의 체스판 만들기 가능

🙏 참고

• 그동안 접했던 문제 중에 가장 어렵다고 느꼈는데 아래 블로그를 보고 도움을 많이 받았다!

👉 [백준 알고리즘/python] 백준 1018 체스판 다시 칠하기, 파이썬 설명