[BOJ]1018. 체스판 다시 칠하기

문제:

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검정색으로 칠해져있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.

하지만 지민이는 이 보드가 체스판처럼 검점/흰색 패턴이 번갈아가며 색칠해져있기 않기 때문에 고민에 빠졌다. 따라서 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야 겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다.

현재 보드의 색이 어떤지 상태가 주어질 떄, 지민이가 8*8크기로 자른 뒤에 다시 칠해야하는 정사각형 개수의 최솟값을 구하는 프로그램을 작성하시오.

체스판은 각 정사각형이 검정 또는 흰색이며, 변을 공유하는 두 개의 사각형이 같은 색이 아닐 때이다. 따라서 위 정의에 의하면 체스판의 색은 항상 두 가지가 가능한데, 하나는 왼쪽 위 코너가 흰색인 것, 검정색인 것 두가지이다.

입력:

첫째 줄에 N과 M이 주어진다. M과 N은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개 줄에는 체스판의 색 상태가 주어진다. B는 검정색이며, W는 흰색이다.

출력:

첫째 줄에 지민이가 8*8 크기로 자른 뒤에 다시 칠해야하는 정사각형 개수의 최솟값을 출력한다.

풀이 방법:

부르트포스를 이용해 모든 경우의 수를 파악해보면 된다. 왼쪽 위부터 8*8 체스판을 골라서 그 중에 몇 개를 색칠해야하는지 세어본다. 이후 옆으로 한 칸씩, 아래로 한 칸씩 이동하면서 잘못된 배열을 찾아 세는 작업을 반복한다. 각 경우마다 센 것을 리스트에 담아두고 제일 작은 값을 출력하도록 한다.

a,b=map(int,input().split())
board=[]
for i in range(a):
    line=input().split()
    board.append(line)
minlist=[]
for i in range(b-8+1):
    for j in range(a-8+1):
        minW=0
        minB=0
        for p in range(8):
            for k in range(8):
                if (k+p)%2==0:
                    if board[j+p][0][i+k]=='W':
                        minW+=1
                    else:
                        minB+=1
                else:
                    if board[j+p][0][i+k]=='B':
                        minW+=1
                    else:
                        minB+=1
        minlist.append(min(minB,minW))
print(min(minlist))