[백준/파이썬] 25682

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

골드 4 체스판 다시 칠하기 2

💫 알고리즘

누적합 Prefix Sum

배열의 특정 구간 합을 빠르게 계산하기 위한 기법, 미리 누적된 값을 저장하여 활용

누적합 배열을 생성한 후, 구간 합을 O(1) 연산으로 빠르게 조회

쿼리 처리 속도가 매우 빨라짐

---

💡 풀이방향

🐢누적합을 이용하여 KxK 크기의 보드 내 최소 다시 칠해야 하는 개수 계산

1️⃣ 체스판 패턴 생성

(0,0)을 검은색('B')으로 시작하는 체스판(chessB)

(0,0)을 흰색('W')으로 시작하는 체스판(chessW)

2️⃣ 누적합(Prefix Sum) 배열 초기화

다시 칠해야 하는 개수를 저장하는 repaintB, repaintW 두 개의 누적합 배열을 생성

repaintB[i][j]: (0,0) ~ (i - 1, j - 1) 영역에서 chessB로 변경할 때 다시 칠해야 하는 개수

repaintW[i][j]: (0,0) ~ (i - 1, j - 1) 영역에서 chessW로 변경할 때 다시 칠해야 하는 개수  

3️⃣ 누적합 배열 채우기

원본 보드(board)와 두 개의 체스판(chessB, chessW)을 비교

다시 칠해야 하는 칸의 개수를 누적합 배열에 저장

누적합 공식 사용: 

repaint[i + 1][j + 1] = repaint[i][j + 1] + repaint[i + 1][j] − repaint[i][j]

만약 현재 칸도 다시 칠해야 한다면 +1 

4️⃣ K×K 크기의 보드를 검사하며 최소 다시 칠해야 하는 개수 찾기

가능한 모든 K×K 크기의 부분 보드를 확인(해당 영역의 repaint 개수 구하기)

구간 합 공식 사용:

cnt = repaint[i + K][j + K] − repaint[i][j + K] − repaint[i + K][j] + repaint[i][j]

5️⃣ 최솟값 출력

K×K 크기의 모든 보드에서 계산한 값 중 최솟값을 출력

---

🌟 코드 구현 + 👀 풀이

[전체 코드]

import sys
input = sys.stdin.readline

def repaint(N, M, K, board):
    chessB = [[('B' if (i + j) % 2 == 0 else 'W') for j in range(M)] for i in range(N)]
    chessW = [[('W' if (i + j) % 2 == 0 else 'B') for j in range(M)] for i in range(N)]
    
    repaintB = [[0] * (M + 1) for _ in range(N + 1)]
    repaintW = [[0] * (M + 1) for _ in range(N + 1)]
    
    for i in range(N):
        for j in range(M):
            repaintB[i + 1][j + 1] = repaintB[i][j + 1] + repaintB[i + 1][j] - repaintB[i][j]
            repaintW[i + 1][j + 1] = repaintW[i][j + 1] + repaintW[i + 1][j] - repaintW[i][j]
            
            if board[i][j] != chessB[i][j]:
                repaintB[i + 1][j + 1] += 1
            if board[i][j] != chessW[i][j]:
                repaintW[i + 1][j + 1] += 1
    
    min_paint = float('inf')
    
    for i in range(N - K + 1):
        for j in range(M - K + 1):
            repaint_countB = (repaintB[i + K][j + K] - repaintB[i][j + K] - repaintB[i + K][j] + repaintB[i][j])
            repaint_countW = (repaintW[i + K][j + K] - repaintW[i][j + K] - repaintW[i + K][j] + repaintW[i][j])
            min_paint = min(min_paint, repaint_countB, repaint_countW)
    
    return min_paint

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

 

chessB = [[('B' if (i + j) % 2 == 0 else 'W') for j in range(M)] for i in range(N)]

chessW = [[('W' if (i + j) % 2 == 0 else 'B') for j in range(M)] for i in range(N)]

chessB: (0,0)이 검은색('B')으로 시작하는 체스판

chessW: (0,0)이 흰색('W')으로 시작하는 체스판

(i + j) % 2 == 0이면 첫 번째 색상 유지, 1이면 반대 색상 적용

 

repaintB = [[0] * (M + 1) for _ in range(N + 1)]

repaintW = [[0] * (M + 1) for _ in range(N + 1)]

다시 칠해야 하는 개수를 저장할 누적합 배열 초기화

🤔 왜 (N + 1) * (M + 1) 크기로 만들었나요?

🐢 누적합을 쉽게 계산하기 위해서예요!

 

    for i in range(N):
        for j in range(M):
            repaintB[i + 1][j + 1] = repaintB[i][j + 1] + repaintB[i + 1][j] - repaintB[i][j]
            repaintW[i + 1][j + 1] = repaintW[i][j + 1] + repaintW[i + 1][j] - repaintW[i][j]
            
            if board[i][j] != chessB[i][j]:
                repaintB[i + 1][j + 1] += 1
            if board[i][j] != chessW[i][j]:
                repaintW[i + 1][j + 1] += 1

repaint[i + 1][j + 1] = repaint[i][j + 1] + repaint[i + 1][j] - repaint[i][j]

누적합 공식을 사용하여 다시 칠해야 하는 개수 저장

repaint[i][j + 1]: 왼쪽 부분 합

repaint[i + 1][j]: 위쪽 부분 합

- repaint[i][j]: 중복된 부분을 제거

if board[i][j] != chess[i][j]: repaint[i + 1][j + 1] += 1

현재 칸을 비교하여 다시 칠해야 하면 +1

 

    for i in range(N - K + 1):
        for j in range(M - K + 1):
            repaint_countB = (repaintB[i + K][j + K] - repaintB[i][j + K] - repaintB[i + K][j] + repaintB[i][j])
            repaint_countW = (repaintW[i + K][j + K] - repaintW[i][j + K] - repaintW[i + K][j] + repaintW[i][j])
            min_paint = min(min_paint, repaint_countB, repaint_countW)

가능한 모든 K×K 크기의 체스판을 탐색 (N - K + 1) * (M - K + 1)번 반복

count = repaint[i + K][j + K] − repaint[i][j + K] − repaint[i + K][j] + repaint[i][j]

누적합을 사용하여 구간합 계산

min_paint = min(min_paint, repaint_countB, repaint_countW)

min_paint를 계속 업데이트하여 최솟값 찾기