백준 문제 중 1018번, 브루트포스, ‘체스판 다시 칠하기’

백준 문제 중 1018번

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

문제

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

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

---

풀이

입력 받은 체스판 M x N 을 8x8로 쪼갠뒤 체스판 패턴 각각 두 경우를 각각 pat1 pat2라 할때 보드를 쪼갠 케이스마다 pat1 pat2와 비교하고 그 중 값이 작은 경우를 mins 배열에 저장하면 mins는 각 케이스마다의 최소값의 배열이고 mins중 최소값을 찾으면 M x N 중 최소의 경우를 알 수 있다.

from typing import List


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

 # m줄의 문자열을 입력 받을 배열 선언
board = [None for i in range(m)]

 # board를 쪼갠 케이스 들을 저장할 배열 선언
tmp = [None for i in range(8)]

 # board 패턴 입력
for i in range(m):
    board[i] = input()

 # tmp에 초기값 할당
for i in range(8):
    tmp[i] = board[i][0:7]

 # 각 케이스들과 패턴 비교 값 중 작은 수를 저장할 배열
mins = []

 # 체스판 패턴 두가지 경우 선언
pat1 = ['WBWBWBWB','BWBWBWBW']*4
pat2 = ['BWBWBWBW','WBWBWBWB']*4

 # tmp와 pat1 pat2를 비교 후 작은값 return
def find_min(tmp:List[str])->None:

    cnt1 = cnt2 = 0
    
    for i in range(8):

        for j in range(8):

            if tmp[i][j]!=pat1[i][j]:
                cnt1+=1

            if tmp[i][j]!=pat2[i][j]:
                cnt2+=1

    return cnt1 if cnt1<cnt2 else cnt2


 # board를 모든 경우의 8x8기준으로 쪼개서 
 # tmp에 저장    
for i in range(m-7):

    for j in range(n-7):

        for k in range(8):

            tmp[k] = board[k+i][j:j+8]

        x = find_min(tmp)
        mins.append(x)

 # mins배열 중 최소값 출력
print(min(mins))

10 10
BBBBBBBBBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBBBBBBBBB
0

배운점

다뤄야 할 데이터 크기가 커지다 보니 자잘한 실수가 너무 많았다. 좀 더 집중해서 꼼꼼히 보는 연습을 해야겠다.