S4 1018. 체스판 다시 칠하기

문제 보기 :  1018번: 체스판 다시 칠하기

---

문제

• 정답률 : 50%

 

---

작성 코드

n,m = map(int, input().split())
arr = list(list(input()) for _ in range(n))

chb = [['B' if (i+j)%2==0 else 'W' for j in range(8)] for i in range(8)]
chw = [['W' if (i+j)%2==0 else 'B' for j in range(8)] for i in range(8)]

from collections import deque
directions = [(0,1),(1,0)]

def count_arr(board, graph):
    count = 0
    for i in range(8):
        for j in range(8):
            if board[i][j] != graph[i][j]:
                count += 1
    return count

maxx = n*m

for i in range(n-7):
    for j in range(m-7):
        matrix = [ls[j:j+8] for ls in arr[i:i+8]]
        bb = count_arr(matrix, chb)
        ww = count_arr(matrix, chw)
        maxx = min(maxx,bb,ww)

print(maxx)

---

풀이

bfs로 풀이해야할줄 알고 열심히 삽질만 했는데, 생각보다 더 쉬움,,

무조건 8*8 사이즈의 매트릭스를 가지고 비교해야하기 때문에 첫 문자가 b인 chb와 w인 chw를 정의해둔다.

chb는
[['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B']]

chw는
[['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']]

이렇게 만들어두고, 입력으로 받은 행렬을 8*8 크기로 잘라가며 몇개를 변경해야할지 chb, chw와 비교해서 최솟값을 찾는다.