[백준 1018번] 체스판 다시 칠하기 - python

문제 링크

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

1018번: 체스판 다시 칠하기

풀이

- 완전 탐색 문제

- answer : 다시 칠해야 하는 정사각형의 개수는 최대 64로 초기화  

- 가능한 8 * 8 체스판에 대하여 칠해야 하는 체스판의 개수를 모두 확인한다. 

- w_cnt = 0 : (0,0) 위치가 w로 시작할 때 다시 칠해야하는 판의 개수
- b_cnt = 0 : (0,0) 위치가 b로 시작할 때 다시 칠해야 하는 판의 개수 

- graph[x][y]일 때 (x+y) % 2 가 0인 경우는 (0,0)에 칠한 체스판의 색과 같아야 하고

(x+y) % 2 가 1인 경우는 (0,0)에 칠한 체스판의 색과 달라야 한다. 

- 칠해야되는 정사각형의 개수가 작은 것으로 answer 갱신 

n, m = map(int,input().split())

graph = []
# 다시 칠해야 하는 정사각형의 개수는 최대 64 
answer = 64 

for _ in range(n):
  graph.append(list(map(str,input())))

# 8 * 8 체스판을 만들 수 있는 모든 경우의 수에 대하여 탐색 
for i in range(n-7):
  for j in range(m-7):
    w_cnt = 0 # (0,0) 위치가 w로 시작할 때 다시 칠해야하는 판의 개수
    b_cnt = 0 # (0,0) 위치가 b로 시작할 때 다시 칠해야 하는 판의 개수 
    
    for x in range(8):
      for y in range(8):
        index = (x+y) % 2 
        if index == 0:
          # (0,0) 위치가 w로 시작할 때 : w가 아니면 다시 칠해야 하므로 w_cnt + 1 
          if graph[i+x][j+y] != 'W':
            w_cnt += 1 
          # (0,0) 위치가 b로 시작할 때 : b가 아니면 다시 칠해야 하므로 b_cnt + 1 
          if graph[i+x][j+y] != 'B':
            b_cnt += 1
        else:
          # (0,0) 위치가 w로 시작할 때 : b가 아니면 다시 칠해야 하므로 w_cnt + 1 
          if graph[i+x][j+y] != 'B': 
            w_cnt += 1 
          # (0,0) 위치가 b로 시작할 때 : w가 아니면 다시 칠해야 하므로 b_cnt + 1 
          if graph[i+x][j+y] != 'W':
            b_cnt += 1
    # 칠해야 하는 체스판의 개수가 작은 것으로 갱신 
    answer = min(answer, b_cnt, w_cnt)

print(answer)