백준 25682번: 체스판 다시 칠하기 2 [python]

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

---

문제 접근

https://www.acmicpc.net/problem/1018
예전에 풀었던 문제 '1018번: 체스판 다시 칠하기' 에 다른 버젼인 문제이다.
그때는 8보다 크거나 같은 수 M,N을 입력받아 무조건 8*8 로 잘라서 체스판을 완성시키는 문제 였다면,

지금 만난 25682번은 M,N 을 입력받고 임의의 수 K*K 로 잘라낸 뒤 체스판을 완성시킬때, 다시 칠해야 하는 정사각형의 최소 개수를 구하면 된다.

해당 문제를 누적합 으로 풀기 위해서는 2차원 배열 누적합에 대해 이해해야 한다.

2차원 배열 누적합

우리는 1차원 누적합에 대해 알고있다.
i~j번째 까지의 부분합을 구하고 싶다면
S[j] - S[i-1] 을 구하면 된다.
부분합 = 두 누적합의 차이

ex)
순열 [1,2,3,4,5]
누적합 S [1,3,6,10,15]
2~4 부분합 = S[4]-S[1] = 10 - 1 = 9

2차원 배열은?

2차원 배열에서 빨간색 박스의 누적합 (0,0)~(i,j) 는
노란색 박스 4 + 초록색 박스 3 - 겹치는 부분 2 에다가 갈색박스 5를 더해주면 된다.

prefixSum[i][j] = 
prefixSum[i][j-1] # 노란색 박스 4
+ prefixSum[i-1][j] # 초록색 박스 3
- prefixSum[i-1][j-1] # 겹치는 파란색박스 2
+ arr[i-1][j-1] # 갈색 박스인데 이때, arr 보다 prefixSum의 인덱스가 1씩 크기 때문에 i-1,j-1 처리

2차원 부분합

누적합을 사용하면 (i,j)에서 (x,y)까지의 부분합을 O(1)에 구할 수 있다.
단, prefixSum은 (0,0)부터 (i,j)까지의 누적합이므로, 인덱스를 1씩 늘려서 다룬다.

5번 갈색 구역의 부분합을 구하기 위해서는
1번 빨간색 prefixSum[x+1][y+1]에서
3번 초록색 prefixSum[i][y+1]을 빼고,
4번 노란색 prefixSum[x+1][j]을 빼고,
중복으로 빠진 2번 파란색 prefixSum[i][j]를 더한다.

점화식:

partSum = (
    prefixSum[x+1][y+1]
  - prefixSum[i][y+1]
  - prefixSum[x+1][j]
  + prefixSum[i][j]
)

그림 출처 :https://code-angie.tistory.com/22

---

그래서 여기서 누적합 어떻게 써먹냐면

체스판을 검사하고싶다.

그런데 매번 눈으로 직접 칸을 세면 너무 오래 걸린다.

그래서 먼저 "틀린 칸 표시판"을 만들고 (== diff 배열)

그 표시판을 누적합으로 바꿔서 (== prefix 배열)

KxK 안에 틀린 칸이 몇 개인지 한 번에 딱 계산하려 한다.

해답 및 풀이

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
board = [input().rstrip() for _ in range(N)]

# 'W'로 시작하는 체스판 기준으로만 diff 계산
diff = [[0] * M for _ in range(N)]
for i in range(N):
    for j in range(M):
        expected = 'W' if (i + j) % 2 == 0 else 'B'
        if board[i][j] != expected:
            diff[i][j] = 1  # 틀렸으면 1

# prefixSum 계산 (1-based indexing)
prefix = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(M):
        prefix[i+1][j+1] = (
            prefix[i+1][j] +
            prefix[i][j+1] -
            prefix[i][j] +
            diff[i][j]
        )

# 최소 repaint 찾기
answer = float('inf')
for i in range(N - K + 1):
    for j in range(M - K + 1):
        y1, x1 = i, j
        y2, x2 = i + K, j + K
        repaint = (
            prefix[y2][x2]
            - prefix[y1][x2]
            - prefix[y2][x1]
            + prefix[y1][x1]
        )
        # 시작이 'W' or 'B' 둘 다 고려
        answer = min(answer, repaint, K*K - repaint)

print(answer)

아직 행, 열 개념이 익숙하지 않아서 더욱 이해하는데 어려웠다.
prefix[y][x] 순으로 쓰는 것도 2차원 배열이 내부적으로 list of list 행 중심 구조 이기 때문이라고 한다.

그래도 2차원 누적합,부분합 개념은 조금 받아들인 것 같다.