[Python] 백준 - 25682 체스판 다시 칠하기 2

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 K×K 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 잘라낸 K×K 보드를 체스판으로 만들기 위해 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

제한

• 1 ≤ N, M ≤ 2000
• 1 ≤ K ≤ min(N, M)

 

필요한 도구

 

1. 2차원 누적합을 저장할 자료구조 : pre

 

2. 체스판의 검정, 하양 공간에 따라 수정할 부분을 카운팅할 함수 : mini(color)

 

3. 위 함수로 계산된 pre를 이용해 주어진 k x k 체스판에 맞는 최소값을 찾기 : scale(pre)

 

 

문제해결방법

 

1. 누적합은 [1, 2, 3, 4, 5] 라는 배열이 있다면 [1, 3, 6, 10, 15] 처럼 각 배열의 요소들을 누적해서 더해주는 방법이다.

1-1. 위 배열을 pre라고 하고, 두번째부터 네번째까지의 누적합(2+3+4 = 9)을 구하려고 한다면, pre[4번째]-pre[두번째-1]으로 구할 수 있다.

 

 

2. 2차원 누적합은 다음과 같다.

1-1. 누적합 배열을 구성하는 방법은 pre[i][j-1] + pre[i-1][j] + 원래배열에 해당하는 값[i][j] - pre[i-1][j-1] 이다.

1-2. (x, y)부터 (i, j)까지의 누적합을 검색하는 방법은 pre[i][j] - pre[i][y-1] - pre[x-1][j] + pre[x-1][y-1]이 된다.

3. 체스판을 자르는 방법은 다음과 같다.

 

 

-코드

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
d = [input().strip() for _ in range(n)]

def mini(color):
	pre = [[0 for _ in range(m+1)] for _ in range(n+1)]
	for i in range(1, n+1):
		for j in range(1, m+1):
			if (i+j) % 2 == 0:
				p = d[i-1][j-1] != color
			else:
				p = d[i-1][j-1] == color
			pre[i][j] = p + pre[i][j-1]+pre[i-1][j] - pre[i-1][j-1]
	print(pre)
	return pre

def scale(pre):
	cnt = sys.maxsize
	for i in range(1, n-k+2):
		for j in range(1, m-k+2):
			P = pre[i+k-1][j+k-1] - pre[i+k-1][j-1] - pre[i-1][j+k-1] + pre[i-1][j-1]
			cnt = min(cnt, P)
	return cnt

print(min(scale(mini('B')), scale(mini('W'))))