[BOJ] 1018. 체스판 다시 칠하기

Problem

BOJ 1018. 체스판 다시 칠하기

지민이는 $N \times M$ 크기의 보드를 잘라서 $8 \times 8$ 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다.

다시 칠해야 하는 정사각형의 최소 개수를 구하시오.

• $8 \le N, M \le 50$

Input:
10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
...

Output:
12

---

Initial Thought (Failed)

혹시 그리디 알고리즘으로 해결할 수 있을까요? 현재 칸을 다시 칠하는 것이 이득인지 그때그때 판단하면 안 될까요?

• 안 됩니다. 첫 칸을 칠하지 않는 것이 최적일 수도 있고, 칠하는 것이 최적일 수도 있습니다. 전체 $8 \times 8$ 패턴을 완성해봐야 알 수 있습니다.

---

Key Insight

$8 \times 8$ 체스판이 될 수 있는 패턴은 단 두 가지뿐입니다!

1. 맨 위 왼쪽이 흰색(W)으로 시작하는 경우
2. 맨 위 왼쪽이 검은색(B)으로 시작하는 경우

입력 크기가 $N, M \le 50$으로 매우 작으므로, 모든 가능한 $8 \times 8$ 영역을 잘라내어 두 가지 패턴과 비교해보는 Brute Force (완전 탐색) 방식이 가능합니다.

---

Step-by-Step Analysis

$8 \times 8$ 체스판을 만들기 위해 $(i, j)$를 시작점으로 잡았을 때:

graph TD
    S["Start at (i, j)"] --> P1["Pattern 1: Top-Left White"]
    S --> P2["Pattern 2: Top-Left Black"]
    
    P1 --> C1{"Count Mismatches"}
    P2 --> C2{"Count Mismatches"}
    
    C1 --> R1["Cost W"]
    C2 --> R2["Cost B"]
    
    R1 --> M["Min(Cost W, Cost B)"]
    R2 --> M
    M --> F["Global Min Update"]

1. Iterate: $N-7$행, $M-7$열까지 시작점 $(i, j)$ 순회.
2. Check: 각 시작점에서 $8 \times 8$ 영역 내부 스캔.
3. Count: (row + col) % 2에 따라 색이 맞는지 확인.

---

Solution

import sys

# 입력 받기
input = sys.stdin.readline
N, M = map(int, input().split())
board = [input().strip() for _ in range(N)]

min_repaint = float('inf')

# 1. 가능한 모든 8x8 시작점 순회
for i in range(N - 7):
    for j in range(M - 7):
        cost_start_w = 0
        cost_start_b = 0
        
        # 2. 8x8 영역 내부 검사
        for x in range(i, i + 8):
            for y in range(j, j + 8):
                current_color = board[x][y]
                
                # (x + y)의 합이 짝수/홀수냐에 따라 기대되는 색이 결정됨
                is_even_sum = (x + y) % 2 == 0
                
                # Case 1: Start with 'W' (Even sum -> W, Odd sum -> B)
                if is_even_sum:
                    if current_color != 'W': cost_start_w += 1
                    if current_color != 'B': cost_start_b += 1
                else:
                    if current_color != 'B': cost_start_w += 1
                    if current_color != 'W': cost_start_b += 1
                # end if
            # end for
        # end for
        
        min_repaint = min(min_repaint, cost_start_w, cost_start_b)
    # end for
# end for

print(min_repaint)

---

Complexity

• Time Complexity: $O(NM)$
  • 정확히는 $(N-7)(M-7) \times 64$ 번의 연산.
  • 최대 연산 수 $\approx 43 \times 43 \times 64 \approx 120,000$회로 매우 적습니다.
• Space Complexity: $O(NM)$
  • 보드 저장 공간.

---

Key Takeaways

Point	Description
Brute Force	입력 크기가 작을 때 가장 확실한 해법
Chessboard Pattern	(r+c) % 2를 이용하여 격자 무늬 패턴을 쉽게 검사 가능
Search Space	$(N-7) \times (M-7)$ 개의 모든 부분 체스판을 탐색