[백준] 1018. 체스판 다시 칠하기

문제

풀이

처음에는 입력의 크기를 주의깊게 보지 않아서 완전탐색의 방식을 생각하지 못했다. 다른 방법을 아무리 생각해봐도 떠오르지 않아서 천천히 다시 생각해봤는데 N과 M의 범위가 50이고 가능한 모든 8x8 정사각형을 검사하더라도 충분히 커버 가능하다고 생각해서 완전탐색으로 풀었다.

완전탐색을 할 때, 처음 시작이 W인 경우와 B인 경우 모두 수행하도록 했다. 조금 헤맸던 부분은 prev를 유지하면서 prev와 현재 값이 같으면 카운트를 해주는 방식으로 구현했는데 줄이 바뀔 때마다 prev의 값이 한 번 더 변경되어야 하는 부분이었다. 그래서 처음 행을 제외한 모든 행의 첫 열은 prev를 한 번 더 변경해주는 방식으로 구현하였다. 구현 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static char[][] input;

	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine()); // "2 3"을 한줄로 입력받기
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		input = new char[N][M];

		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < M; j++) {
				input[i][j] = line.charAt(j);
			}
		}

		int min = Integer.MAX_VALUE;
		for (int x = 0; x <= N - 8; x++) {
			for (int y = 0; y <= M - 8; y++) {
				min = Integer.min(min, getCount(x, y, 'W'));
				min = Integer.min(min, getCount(x, y, 'B'));
			}
		}
		System.out.println(min);
	}

	private static int getCount(int x, int y, char start) {
		char prev = start;
		int cnt = (input[x][y] == start) ? 0 : 1;

		for (int i = x; i < x + 8; i++) {
			for (int j = y; j < y + 8; j++) {
				
				if (i == x && j == y) continue;
				if (j == y) {
					prev = ( prev == 'W') ? 'B' : 'W';
				}
				
				if (prev == input[i][j]) {
					cnt++;
				}
				prev = ( prev == 'W') ? 'B' : 'W';
			}
		}
		return cnt;
	}
}