브루트포스. 체스판 다시 칠하기

문제

MxN 배열에서 8x8 체스판을 떼어내는 경우의 수중 최소로 고칠수있는 경우 구하기.

해결방향성

사실 이 문제를 풀고나서 브루트포스는 문제를 잘 읽어야겠다는 생각을 했다.
문제에 정답이 다 나와있다. 이 문제는 MxN개의 배열에 맞춰서 체스판을 제작하는 것이 아니라, MxN 배열에서 8x8 부분을 떼어오는 문제이다. 게다가 체스판은 흑백으로 번갈아가며 칠하기 때문에, 두가지 경우밖에 생기지않는다.
1. 첫째칸을 검은색으로 먼저 칠하는 경우
2. 첫째칸을 흰색으로 먼저 칠하는 경우
이 두가지 경우의 8x8 배열을 먼저 구한 후, MxN 배열에 맞춰 잘라서 경우의 수를 구하면된다.
다시말하면, (M - 8)x(N - 8)개의 경우의 수가 생긴다.
이 경우의 수에 따라 8x8 배열과 비교한 후 최소값을 구하면된다.

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static char[][] chess;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken()); // column
        N = Integer.parseInt(st.nextToken()); // row

        chess = new char[M][N];

		// 체스판 입력받기
        for (int row = 0; row < M; row++) {
            String str = br.readLine();
            for (int column = 0; column < N; column++) {
                chess[row][column] = str.charAt(column);
            }
        }

        // 올바른거 하나 두고 다른거 카운트 : 검은색으로 시작, 하얀색으로 시작
        char[][] blackChess = new char[8][8];
        char[][] whiteChess = new char[8][8];

        makingChess(blackChess, 'W');
        makingChess(whiteChess, 'B'); // 거꾸로 되므로 거꾸로 color 대입

		// 경우의 수를 구하기 위한 차이 구하기
        int subRow = M - 8;
        int subColumn = N - 8;
        // 최소값의 초기화는 반대로 최대값으로 한다.
        int min = Integer.MAX_VALUE;
        
        // 경우의 수에 따라 최소가 되는 경우 체크
        for (int i = 0; i <= subRow; i++) { // 2
            for (int j = 0; j <= subColumn; j++) { // 5
                min = Math.min(min,check(blackChess, i, j));
                min = Math.min(min,check(whiteChess, i, j));
            }
        }

        bw.write(String.valueOf(min));

        bw.flush();
        br.close();
        bw.close();
    }

	// 최소값 체크 함수
    private static int check(char[][] answer, int row, int column) {
        int count = 0;
        for (int i = row; i < row + 8; i++) {
            for (int j = column; j < column + 8; j++) {
                if (answer[i - row][j - column] == chess[i][j]) {
                    continue;
                }
                count++;
            }
        }
        return count;
    }

	// 초기 체스판을 만드는 함수
    private static void makingChess(char[][] chess, char color) {
        chess[0][0] = color; // W
        // 이게 반대로 넣어야하는데 내부 함수 구조가  'B' -> 'W'로 바꾸는 형태이기 때문

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (color == 'B') {
                    chess[i][j] = 'W';
                    color = 'W';
                } else {
                    chess[i][j] = 'B';
                    color = 'B';
                }
            }
            // 짝수 column일때는 다음 행 값이 그대로 유지 되어야한다.
            if (color == 'B') {
                color = 'W';
            } else {
                color = 'B';
            }
        }
    }


}

결론

다시 풀어보는 문제. 주목 할 점은
1. 체스판의 경우의 수가 2개밖에 없다는 점과,
2. 8x8형태로 체스판을 자른다는 점.
두가지 경우를 생각해 브루트포스로 구한다.
출처 : https://st-lab.tistory.com/101 에서 변형시켰다.