1018: 체스판 다시 칠하기 - Python

문제

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

드디어 풀었다 이 지긋지긋한 놈

풀이

N, M = map(int, input().split())
board = [input() for _ in range(N)]
W_board = ("WB"*4+"BW"*4)*4
B_board = ("BW"*4+"WB"*4)*4
min_diff = 64

for x in range(M-7):
    for y in range(N-7):
        sub_board = "".join([row[x:x+8] for row in board[y:y+8]])
        
        W_diff, B_diff = 0, 0
        for i, j in zip(sub_board, W_board):
            if i != j:
                W_diff += 1
        for i, j in zip(sub_board, B_board):
            if i != j:
                B_diff += 1
        
        diff = min(W_diff, B_diff)
        if diff < min_diff:
            min_diff = diff
print(min_diff)

코드 설명

• N, M, board: 입력값
• W_board: "WBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBW"
• B_board: "BWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWB"
• min_diff: 구하는 값 (다시 칠해야 하는 칸 수의 최소값)

1. for x in range(M-7), for y in range(N-7): sub_board의 시작점인 (x, y)를 순회
   • 
   • 
2. sub_board: 전체 체스판(board)에서 (x, y)를 시작점으로 8x8로 자른 체스판을 문자열로 저장
   • 예시) sub_board = "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBW"
3. sub_board와 W_board, B_board의 차이를 구해 각각 W_diff, B_diff에 저장
4. W_diff, B_diff 중 더 작은 것을 골라 diff에 저장
5. 만약 diff가 현재까지의 min_diff보다 작다면 min_diff를 갱신
6. 모든 sub_board에 대해 계산을 완료하면 min_diff를 출력

3줄 요약
1) 입력받은 체스판(board)에서 모든 가능한 8x8 체스판(sub_board)을 잘라낸다.
2) 잘라낸 8x8 체스판을 두 가지의 패턴(W_board, B_board)과 비교해 칠해야 하는 칸의 수(diff)를 계산한다.
3) 이렇게 모든 8x8 체스판을 순회하며 칠해야 하는 칸 수의 최소값(min_diff)을 구한다.

사실 도저히 아이디어가 안떠올라서 GPT한테 힌트 좀 달라고 했고,
"가능한 모든 경우의 8x8 체스판을 생각해보라"는 대답을 듣고 이를 브루트포스로 구현했다.