문제
N×M 크기의 보드가 검은색(B)과 흰색(W)으로 칠해져 있다. 이 보드에서 8×8 크기의 체스판을 잘라내어 올바른 체스판으로 만들기 위해 다시 칠해야 하는 칸의 최소 개수를 구하라.
입력
첫째 줄에 N, M이 주어진다 (8 이상 50 이하). 둘째 줄부터 N줄에 보드의 각 행 상태가 B와 W로 주어진다.
출력
다시 칠해야 하는 칸의 최소 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW | 0 |
풀이
모든 가능한 8×8 위치에 대해 체스판 패턴과 비교하여 다시 칠해야 하는 칸 수의 최솟값을 구한다.
- 보드를 B=1, W=0으로 변환하여 2차원 배열에 저장한다
- (i, j)부터 시작하는 모든 8×8 영역을 탐색한다
- 각 영역의 좌상단 칸을 기준으로 체스판 패턴과 비교하여 불일치 수를 센다
- 좌상단이 B인 경우와 W인 경우 두 패턴이 있으므로
cnt와64-cnt중 작은 값을 취한다 - 모든 영역 중 최솟값을 출력한다
핵심 아이디어: 체스판은 (i+j)가 짝수/홀수인 위치에 같은/다른 색이 번갈아 오므로, 한쪽 패턴의 불일치 수를 세면 반대 패턴의 불일치 수는 64-불일치가 된다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day29BOJ1018체스판다시칠하기브루트포스 { // 1018 체스판 다시 칠하기
static int[][] chess;
static int min = 111;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
chess = new int[N][M];
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++) {
chess[i][j] = str.charAt(j) == 'B' ? 1 : 0;
}
}
for (int i = 0; i < N - 7; i++) {
for (int j = 0; j < M - 7; j++) {
check(i, j);
}
}
System.out.println(min);
br.close();
}
private static void check(int idx, int jdx) {
int cnt = 0;
int first = chess[idx][jdx];
for (int i = idx; i < idx + 8; i++) {
for (int j = jdx; j < jdx + 8; j++) {
if (chess[i][j] != first) {
cnt++;
}
first = (first + 1) % 2;
}
first = (first + 1) % 2;
}
cnt = Math.min(cnt, 64 - cnt);
min = Math.min(min, cnt);
}
}복잡도
- 시간: O((N-7) * (M-7) * 64) — 모든 8×8 위치에 대해 64칸 비교
- 공간: O(N * M) — 보드 배열