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

문제

입출력

시도

# 백준 체스판 다시 칠하기 브루트포스 실버4
import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))
board = [input() for _ in range(N)] # 보드 입력
m = [100 for i in range((M-7)*(N-7))] # 각 구역 최소값

res = 0
for i in range(N-7):
    for j in range(M-7):
        for k in board[i][j::4]:
            if board[i][j] != board[i+2][j]:
                res+=1
            if board[i][j+1]==board[i][j] and board[i][j+1] != board[i][j+3]:
                res += 1
    m[i*j]= res
print(min(m))

아래로 내려가면서 2간격 차이나는 알파벳이 다른지 검사하려 함
문제 : 좌우는 검사할 수 없음

구글링 ㄱㄱ

해설

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

요점은 가로가 아닌 '대각선'으로 검사임

또한 내가 놓친 점이 있는데 왼쪽 위가 흰색일 때와 검은색일 때의 경우를 둘다 고려해야 함.
나는 그냥 현재 상태에서 틀린 부분을 찾아내어 +1 하려고 했는데 그렇게는 해결할 수 없음.

1. 왼쪽 위가 흰색이어야 할 때, 현재의 부분 타일에서 고쳐야 하는 부분의 개수
2. 왼쪽 위가 검은색이어야 할 때, 현재의 부분 타일에서 고쳐야 하는 부분의 개수
   두가지를 결과 리스트에 담아서 최소값을 골라내야 함

처음에는 풀이를 보고도 이해가 잘 안됐는데, 그림을 그려보니 이해가 간다.
위의 타일은 왼쪽 위가 검은색어야 할 때 고쳐야 할 부분은 없지만, 하얀색이어야 할 때는 전부 다 고쳐야 한다.

이럴 때의 정답은? 0이다.

그렇다면 이 타일은 어떤가?

왼쪽 위가 검은색이어야 할 때 고쳐야 되는 부분은 7이지만 왼쪽위가 하얀색이어야 할 때 고쳐야 되는 부분은 세기 싫다...아무튼 많다.
즉 이 타일은 검은색을 7번 칠하기만 하면 끝난다!!

즉 왼쪽 위의 색상에 따라 현재 타일의 색상이 유효한지 검사하면 된다

코드

# 백준 체스판 다시 칠하기 브루트포스 실버4
import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))
board = [input() for _ in range(N)] # 보드 입력
res = []

for i in range(N-7):
    for j in range(M-7):
        w = 0 # 왼쪽 맨 위가 흰색일 때 경우의 수
        b = 0 # 왼쪽 맨 위가 검은색일 때 경우의 수 
        for p in range(i, i+8):
            for q in range(j, j+8):
                if (p+q)%2==0: # 왼쪽 위와 색이 같아야 하는 곳
                    #왼쪽 위가 흰색인 경우 해당 타일이 흰색이어야 되는데 그렇지 않을 때
                    if board[p][q] != 'W' :
                        w +=1
                    #왼쪽 위가 검은색인 경우 해당 타일이 검은색이어야 되는데 그렇지 않을 때
                    elif board[p][q] != 'B' : 
                        b += 1
                else :  # 왼쪽 위와 색이 달라야 하는 곳 검사
                    # 왼쪽 위가 흰색인 경우 해당 타일이 검은색이어야 되는데 그렇지 않을 때
                    if board[p][q] != 'B':
                        w += 1
                    elif board[p][q] != 'W':
                        b += 1
        res.append(w)
        res.append(b)
print(min(res))

느낀 점

				if board[p][q] != 'W' :
                        w +=1
                    #왼쪽 위가 검은색인 경우 해당 타일이 검은색이어야 되는데 그렇지 않을 때
                    elif board[p][q] != 'B' : 
                        b += 1
                else :  #홀수번째 칸 검사
                    # 왼쪽 위가 흰색인 경우 해당 타일이 검은색이어야 되는데 그렇지 않을 때
                    if board[p][q] != 'B':
                        w += 1
                    elif board[p][q] != 'W':
                        b += 1

이 부분이 진짜 이해가 안되더라... 아니 지금 왼쪽 위가 검은색인데 하얀색 아니라고 경우의 수를 늘리는 게 어딨어!! 이랬음ㅋㅋㅋㅋ

브루트포스를 해결하기 위한 마음가짐을 잘 가져야겠다...