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

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

import sys

read = sys.stdin.readline

h, w = list(map(int, read().split()))

board = []
result = []
for _ in range(h):
  board.append(input())

# h-7 w-7 하는 이유?
# 8*8 체스판을 만들어야 하는데, 인덱스를 벗어나면 안되기 때문
for i in range(h-7):
  for j in range(w-7):
    first_w = 0
    first_b = 0
    for row in range(i, i+8):
      for col in range(j, j+8):
        # 행,열의 합을 짝 / 홀 기준으로 나눈 이유?
        # 행,열의 합 중 짝끼리, 홀끼리 색이 같기 때문
        if(row+col) % 2 == 0:
          if board[row][col] != 'W':
            first_w += 1
          if board[row][col] != 'B':
            first_b += 1
        else:
          if board[row][col] != 'W':
            first_b += 1
          if board[row][col] != 'B':
            first_w += 1
    result.append(first_w)
    result.append(first_b)

print(min(result))

4중 for문을 써야하는 문제이고 아이디어를 떠올리기 쉽지 않은 문제인 것 같다...(내기준😥)

1,2번째 for문은 8*8 크기의 체스판을 떼어낼 수 있는 경우의 수에 대해 생각한다. -7을 해준 이유는 8칸이 기존 보드에서 넘어가지 않도록 하기 위함이다.

Ex) 9*9 보드판에서 8*8 체스판을 선택할 수 있는 경우의 수는 (0,0)부터 자르는 경우와 (1,0), (0,1), (1,1) 일 때 가능하다.

 

3,4번째 for문은 첫번째 시작이 흰색일 경우와 검은색일 경우를 고려해 주는 것이다. 

행과열의 인덱스 합이 짝수면 시작네모의 색과 똑같고 홀수면 다르다. 이 특징을 이용해 준 것이다.

 

문제는 색을 수정해야 하는 경우를 생각하는 것이기 때문에 행,열의 합이 짝수 인데 흰색이 아니라면 first_w(시작이 흰색인 경우)의 값을 올려준다. (시작이 흰색이었을 때 틀린경우가 되므로 first_w 값을 올려주어야 함)

 

그 중 최솟값을 구하면 되기 때문에 그 후 과정은 간단하다.