[백준 - Python] 1018. 체스판 다시 칠하기 (완전 탐색)

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

1018번: 체스판 다시 칠하기

 

코드

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

board = []
for i in range(n):
    board.append(input())

result = []
for i in range(n - 7):
    for j in range(m - 7):
        c1 = 0
        c2 = 0
        for k in range(i, i + 8):
            for l in range(j, j + 8):
                if (k + l) % 2 == 0:
                    if board[k][l] != 'W':
                        c1 += 1
                    if board[k][l] != 'B':
                        c2 += 1
                else:
                    if board[k][l] != 'W':
                        c2 += 1
                    if board[k][l] != 'B':
                        c1 += 1
        result.append(c1)
        result.append(c2)

print(min(result))

 

처음에 문제를 읽고

전체적인 접근은 비슷하게 떠올렸지만,

핵심 아이디어는 떠올리지 못했다.

 

보드 전체를 돌면서 현재 칸의 색과

현재 칸의 오른쪽 칸의 색이 다르면

변경해주고 카운팅을 해주는 방식으로 접근을 했는데

이러한 방식으로 카운팅을 해주면

매 경우의 수마다 보드를 복사하고 값을 변경해주는 과정을 거쳐야 했다.

 

다른 분들의 코드를 참고해보니

(k + l) % 2

 

라는 수식을 통해

체스판에서 같은 색이 칠해져야 하는 부분을 구분했다.

 

문제에서

"체스판을 색칠하는 경우는 두 가지 뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우"라는 명세를 보고

만들 수 있는 체스판의 경우가 2가지 임을 인지하고

경우를 나누어서 카운팅하여 최솟값을 구해야 했다.

 

또한 2차원 배열에 접근하기 위해

반복문으로 배열의 인덱스를 생성할 때,

어떤 값으로 생성하는 지에 따라서

코드를 짤 때 인덱스가 간결해질 수 있다는 점을 염두하고 문제를 풀자!

 

코드에서

for k in range(i, i + 8):
            for l in range(j, j + 8):

 

8x8 배열을 확인하는 이중 반복문의 인덱스 생성 범위를

다음과 같이 설정하면

이중 반복문 내부에서 이차원 배열 인덱싱을 간결하게 표현할 수 있다.

 

해당 문제도 N, M의 크기가 100보다 작음으로

완전 탐색으로 풀어야겠다는 생각이 가능했다.

 

완전 탐색 유형임을 파악하는 것보다

체스판에서 같은 색이 칠해져야 하는 부분을 구분하는 수식을 떠올리는 부분이 더 어려웠던 문제다.