[Python] 백준 1018 체스판 다시 칠하기

1. 문제 - 백준 1018 체스판 다시 칠하기

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

 

💡알고리즘 - 구현

• 입력받은 보드에서 모든 8x8 크기의 체스판을 잘라 다시 칠해야하는 정사각형의 갯수를 구하는 문제이다.

✅ 풀이

import copy

n, m = map(int, input().split())  # mxn 크기의 보드
board = []
for _ in range(n):
  board.append(list(input()))
  
answer = int(1e9)

def simulation(x, y, board):  # 8x8 함수에서 칠해야하는 정사각형의 갯수 구하는 함수
  # 처음이 B인지 W인지에 따라 칠해야하는 갯수가 달라진다.
  w_index=0 # W로 시작하는 보드에서 칠하는 갯수
  b_index=0 # B로 시작하는 보드에서 칠하는 갯수
  for i in range(x,x+8):
    for j in range(y,y+8):
      if (i+j)%2==0: # 짝수라면, 시작과 동일해야한다.
        if board[i][j] == "B":#B이면
          w_index+=1 #W로 시작하는 보드이므로 B -> W로 칠해야함
        else: #W이면
          b_index+=1 #B로 시작하는 보드이므로 W -> B로 칠해야함
      else: # 홀수라면, 시작과 달라야한다.
        if board[i][j] == "B" :# B이면
          b_index+=1  #B로 시작하는 보드이므로 B -> W로 칠해야함
        else:
          w_index+=1  #W로 시작하는 보드이므로 W -> B로 칠해야함

  return min(w_index, b_index)

for i in range(n-7):  # 처음부터 8x8 보드로 자르며 경우의 수를 판단한다.
  for j in range(m-7):
    answer = min(answer, simulation(i, j, board))

print(answer)

 

- 8x8 크기의 체스판에서 B와 W가 번갈아 나타나는 경우는,
보드의 맨 첫번째가 B로 시작하는 경우와 W로 시작하는 경우의 수가 서로 다를 것이다.

- W로 시작하는 경우의 보드로 맞추기 위해 기존 보드를 칠해야하는 경우의 수를 w_index
B로 시작하는 경우의 보드로 맞추기 위해 기존 보드를 칠해야하는 경우의 수를 b_index로 나누어 각각 더해보자.

- 예를들어 8x8 보드의 일부로 아래와 같다고 가정해보자.

 

W  (0, 0)	B (0, 1)	B (0, 2)	W (0, 3)
B   (1, 0)	W (1, 1)	B (1, 2)	B (1, 3)

 

- i, j 인덱스의 합이 짝수라면, 시작이 B면 board[i][j]가 B여야 하고 시작이 W면 board[i][j]도 W여야한다.

- (0, 2) 위치의 B가 W로 바뀌어야할 것이다. 따라서 w_index + 1 이다. (하단 코드 참고)

  for i in range(x,x+8):
    for j in range(y,y+8):
      if (i+j)%2==0: # 짝수라면, 시작과 동일해야한다.
        if board[i][j] == "B":#B이면
          w_index+=1 #W로 시작하는 보드이므로 B -> W로 칠해야함
        else: #W이면
          b_index+=1 #B로 시작하는 보드이므로 W -> B로 칠해야함

 

- 인덱스의 합이 홀수라면, 시작이 B라면 해당 board[i][j]가 W여야 하고 시작이 W라면 board[i][j]가 B여야한다.

      else: # 홀수라면, 시작과 달라야한다.
        if board[i][j] == "B" :# B이면
          b_index+=1  #B로 시작하는 보드이므로 B -> W로 칠해야함
        else:
          w_index+=1  #W로 시작하는 보드이므로 W -> B로 칠해야함

 

- 정사각형 갯수의 최소값이므로, b_index와 w_index 둘 중 최소값을 return하며 이를 모든 8x8 보드로 순환했을 때의 최소값을 구한다.