백준 #1018: 체스판 다시 칠하기 [Python]

 

접근법

---

문제를 단순화하고 풀고 싶었는데, 이 문제가 브루트포스 단계에 들어간 데에는 이유가 있었다...

 

모든 경우의 수를 고려해주면 되는데, 체스판의 형태는 흰색과 검은색으로 시작되는 경우 두 가지다. 

 

따라서 흰색과 검은색 체스판을 필터라고 생각하고 입력값으로 주어지는 체스판을 한칸 한 칸씩 움직여보면서

 

해당 필터와 비교해서 틀린 칸의 갯수를 세어본다. 여기서 서로 일치하지 않는 칸의 수는 다시 칠해야 하는 칸의 수라고

 

볼 수 있다. 

 

정리하면,

 

첫 번째 : 흰색과 검은색으로 시작하는 체스판을 우선 만들어 둔다. ( 이하 필터로 명명함 )

두 번째 : 입력값으로 주어지는 체스판과 두가지 필터를 한 칸 한 칸씩 모든 경우에 대해서 비교해본다.

세 번째 : 비교해보면서 서로 틀린 칸의 수를 Count한다.

네 번째 : 각각의 경우에서 더 작은 Count 값을 출력한다.

 

 

 

풀이

---

def check_board(SQUARE, probe, move_x, move_y):
    cnt = 0
    for i in range(8):
        for j in range(8):
            if SQUARE[move_x+i][move_y+j] != probe[i][j]:
                cnt += 1
    return cnt


def check_bw():
    
    N, M = map(int,input().split())
    square = [list(input()) for _ in range(N)]
    
    WhiteBoard = [
        ['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']
    ]

    BlackBoard = [
        ['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']
    ]
    
    result = 64
    # 우선 64로 지정한 이유는 8*8 배열에서 모두다 바뀌어야할 때의 숫자다. 
    # 즉 최대값을 우선 넣어두고 overwrite 되도록 하였다.
    
    for i in range(N-7):
        for j in range(M-7):
            W = check_board(square, WhiteBoard, i, j)
            B = check_board(square, BlackBoard, i, j)
            
            result = min(result,W,B)
    
    print(result)
    
check_bw()

 

@ 문제 출처 : 백준