[백준/브루트포스] 1018번 : 체스판 다시 칠하기

- 문제 : https://www.acmicpc.net/problem/1018

 

처음에는 어떻게 풀어야할지 감이 잘 잡히지는 않았는데, 문제에서 "체스판을 칠하는 경우의 수는 왼쪽 가장 위를 검정색, 흰색으로 칠하는 2가지 경우이다." 문구에 힌트를 얻었다. 결국 (0, 0) 값이 검정, 흰색이냐에 따라 체스판 모양이 정해지는 것이기 때문에 주어진 행렬을 8 x 8 로 탐색하면서 두 가지 경우의 체스판과 비교하면서 정답인 체스판과 다른 정사각형의 개수를 각각 구해 그 중에서 최솟값을 출력하면 되겠다 라고 생각했다. 

 

정답 풀이

위 생각을 단계별로 정리하면 다음과 같다. 

1. (0,0)이 검정으로 시작하는 black, 흰색으로 시작하는 white 행렬 미리 만들어 두기

2. 주어진 n x m 행렬(matrix) 8 x 8 단위로 for문 돌리기

3. 8 x 8 행렬의 각 원소값을 black 체스판, white 체스판과 비교하면서 다른 정사각형의 개수를 각각 black_count, white_count에 +1 하기

4. 8 x 8 행렬 탐색이 끝나면 answer = min(answer, black_count, white_count) 진행

5. 모든 단계가 끝나면 answer 최종 출력

 

 

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

matrix = [list(input()) for _ in range(n)]
first = ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B']
second = ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']

black = []
white = []
for i in range(8):
    if i % 2 == 0:
        black.append(second)
        white.append(first)
    else:
        black.append(first)
        white.append(second)
        
answer = 1e9
for i in range(n - 7):
    for j in range(m - 7):
        black_count = 0
        white_count = 0
        for k in range(8):
            for l in range(8):
                if matrix[i + k][j + l] != black[k][l]:
                    black_count += 1
                if matrix[i + k][j + l] != white[k][l]:
                    white_count += 1
                    
        answer = min(answer, black_count, white_count)        
    
print(answer)