★[백준/python] 1018 체스판 다시 칠하기: 브루트포스(전체탐색)/

 

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

1018번: 체스판 다시 칠하기

 

 

-> MxN크기의 보드가 있다.

-> 이 보드를 잘라서 8x8 크기의 체스판으로 만드려고 한다.

-> 체스판은 흰색과 검은색이 번갈아가며 칠해져야 한다.

-> 보드판의 어느부분을 8x8 크기로 잘라낸 후, 고쳐야하는 정사각형을 다시 칠할거다.

->고쳐야 하는 정사각형의 최소 개수를 구해라.

---

여태까지 풀어본 백준 문제 중에 가장 까다로웠다.. ㅜㅜ

https://god-gil.tistory.com/62

 

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

그래서 이 분 코드를 하나하나 해석한 후 써내려갔다.

 

N,M=map(int, input().split())
result=[]
arr=[]
for i in range(N):
  arr.append(input())  # NxM 크기의 보드를 받아온다.

#8X8로 잘라서 나오는 체스판 개수 만큼 반복
for i in range(N-7):
  for j in range(M-7):
    whiteStartCase=0
    blackStartCase=0
    #여기서부터 정해진 8x8 체스판에 대해 바꿔야하는 정사각형 개수를 셀거얌
    #맨 위 왼쪽이 흰색인 경우와 검정색인 경우 두 경우에 대해 바꿔야하는 개수 셀거얌
    for a in range(i,8+i):
      for b in range(j,8+j):
        #a+b가 짝수/홀수 -> 검정/흰 or 흰/검정
        if (a+b)%2==0:
          if arr[a][b]=='W': 
            blackStartCase+=1 #
          else:
            whiteStartCase+=1
        else:
          if arr[a][b]=='W':
            whiteStartCase+=1 #
          else:
            blackStartCase+=1
        
    result.append(whiteStartCase)
    result.append(blackStartCase)

print(min(result)) #최소값 출력