[백준] [구현] [완전탐색] 1018. 체스판 다시 칠하기

1018. 체스판 다시 칠하기

1018번: 체스판 다시 칠하기

 

• 내 풀이 - 오답
  • bfs라고 생각하고 풀었지만 계속 해결방안이 나오지 않음...
  • 처음 시작이 b,w일지 알 수 없어서 시작위치부터 체크하면 뒤랑 맞지 않을 수 있음

 

• 다른 사람 풀이
  • 완전탐색(브루투 포스) 로 풀었어야했음...
  • 처음부터 칠해주기 위해 변수를 선언하는데, 시작 지점이 검은색일 경우와 흰색일 경우를 대비하여 2개의 변수
    • f_w
    • f_b
  • board[a][b] %2= 0일 때와 1일 때를 이용하여 언제 어느 색을 칠할지를 결정
  • 만약 a + b를 2로 나눈 나머지가 0이라면,
    • 검은색이 아닐 때 f_b  +1
    • 흰색이 아닐 때 f_w  +1
    • -> 검은색일 때와 흰색일 때 두 가지 경우를 모두 해결

import sys
input=sys.stdin.readline

n, m =map(int,input().split())
graph=[list(input().rstrip()) for _ in range(n)]

result = []

for i in range(n-7):
    for j in range(m-7):
        f_w = 0 # w로 고쳐야하는 경우
        f_b = 0 # b로 고쳐야하는 경우
        for x in range(i, i+8):
            for y in range(j, j+8):
                if (x+y) % 2 == 0: #같은 문자열이 와야하는 위치
                    if graph[x][y] != 'W': f_w += 1
                    if graph[x][y] != 'B': f_b += 1
                else:
                    if graph[x][y] != 'B': f_w += 1
                    if graph[x][y] != 'W': f_b += 1
        result.append(f_w)
        result.append(f_b)

print(min(result))