문제
N×M 크기의 보드가 주어진다. 보드의 각 칸은 흰색(W) 또는 검은색(B)으로 칠해져 있다. K×K 크기의 올바른 체스판이 되려면 인접한 두 칸의 색이 항상 달라야 한다. 올바른 체스판에서 (1,1) 위치는 흰색이거나 검은색일 수 있다.
N×M 보드에서 K×K 크기의 정사각형 부분을 선택하여 올바른 체스판으로 만들기 위해 다시 칠해야 하는 최소 칸 수를 구하라.
입력
첫 번째 줄에 N, M, K가 주어진다. (1 ≤ K ≤ N, M ≤ 2,000)
이후 N줄에 걸쳐 보드 상태가 주어진다. 각 줄은 M개의 문자로 이루어지며, 'W' 또는 'B'이다.
출력
K×K 크기의 올바른 체스판으로 만들기 위해 다시 칠해야 하는 최소 칸 수를 출력한다.
예제
3 4 2
BWWB
BWWB
WWWB출력:
0풀이
핵심 아이디어: 2차원 누적 합을 두 개 관리한다. 하나는 왼쪽 위(1,1)가 B인 체스판 기준으로 잘못 칠해진 칸의 수, 다른 하나는 (1,1)이 W인 기준으로 잘못 칠해진 칸의 수를 누적한다. 이후 임의의 K×K 부분에 대해 두 경우 중 최솟값이 정답의 후보다.
- 보드를 1-indexed로 읽으면서 각 위치
(i, j)에 대해 두 누적합 배열asum[i][j][0](B 기준 오류),asum[i][j][1](W 기준 오류)을 계산한다. (i+j)%2 == 0이면 B가 와야 하는 자리,(i+j)%2 == 1이면 W가 와야 하는 자리(B 기준 체스판).- K×K 부분 시작점
(r1, c1)에서 끝점(r2, c2)까지의 구간 합을 2D 누적합으로 O(1)에 계산한다. - 두 경우(B 시작, W 시작) 중 최솟값을 전체 정답과 비교한다.
- 총 O(NM) 전처리 후 O((N-K+1)(M-K+1)) 쿼리로 전체 O(NM) 시간 복잡도 달성.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day312BOJ25682체스판 {
static int N, M, K, ans = 2000 * 2000;
static char[][] map;
static int[][][] asum;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new char[N + 1][M + 1];
asum = new int[N + 1][M + 1][2]; // 누적합 배열 0 B 1 W
for (int i = 1; i < N + 1; i++) {
String str = br.readLine();
for (int j = 1; j < M + 1; j++) {
map[i][j] = str.charAt(j - 1);
count(i, j, map[i][j]);
}
}
for (int i = 1; i <= N - K + 1; i++) {
for (int j = 1; j <= M - K + 1; j++) {
solve(i, j, i + K - 1, j + K - 1);
}
}
System.out.println(ans);
br.close();
}
private static void solve(int r1, int c1, int r2, int c2) {
int tmp = 2000 * 2000;
int stB = asum[r2][c2][0] - asum[r1 - 1][c2][0] - asum[r2][c1 - 1][0] + asum[r1 - 1][c1 - 1][0];
int stW = asum[r2][c2][1] - asum[r1 - 1][c2][1] - asum[r2][c1 - 1][1] + asum[r1 - 1][c1 - 1][1];
tmp = Math.min(stB, stW);
ans = Math.min(tmp, ans);
}
private static void count(int r, int c, char color) {
asum[r][c][0] = asum[r - 1][c][0] + asum[r][c - 1][0] - asum[r - 1][c - 1][0];
asum[r][c][1] = asum[r - 1][c][1] + asum[r][c - 1][1] - asum[r - 1][c - 1][1];
if (r % 2 == c % 2) {
if (color == 'W')
asum[r][c][0]++;
else if (color == 'B')
asum[r][c][1]++;
} else {
if (color == 'B')
asum[r][c][0]++;
else if (color == 'W')
asum[r][c][1]++;
}
}
}복잡도
- 시간: O(NM) — 2D 누적합 계산 O(NM) + K×K 슬라이딩 윈도우 O(NM)
- 공간: O(NM) — 2D 누적합 배열 2개