[백준] 1018번 : 체스판 다시 칠하기 - 자바(JAVA)

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

문제 해석

N*M의 보드가 주어집니다.

 

이 보드는 흰색 또는 검정색으로 칠해져있습니다.

 

여기에서 8x8 크기의 체스판으로 잘라낸 후 체스판처럼 칠하고자 합니다.

 

이때 체스판처럼 이미 칠해져 있으면 가장 좋은 경우입니다.

 

다시 칠해야 하는 정사각형의 최소 개수를 구하세요

 

문제 풀이 전 설계

8 x 8 크기의 검정색으로 시작하는 체스판, 흰색으로 시작하는 체스판을 미리 그려놓습니다.

그리고 보드를 (0,0) ~ (N-8, M-8) 를 시작점으로 두고 8 x 8 크기로 얼마나 일치하는지를 검사하면서 최소값을 갱신하며 값을 구합니다.

 

코드

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

public class Main_1018_체스판다시칠하기 {

    final static int BOARD_SIZE = 8;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        final int N = Integer.parseInt(st.nextToken());
        final int M = Integer.parseInt(st.nextToken());

        final char[][] board = new char[N][M];

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

        char[][] whiteChessBoard = new char[BOARD_SIZE][BOARD_SIZE];
        char[][] blackChessBoard = new char[BOARD_SIZE][BOARD_SIZE];

        boolean isBlack = true;
        for (int i = 0; i < BOARD_SIZE; i++) {
            isBlack = i % 2 == 0 ? true : false;
            for (int j = 0; j < BOARD_SIZE; j++) {
                whiteChessBoard[i][j] = isBlack ? 'B' : 'W';
                blackChessBoard[i][j] = !isBlack ? 'B' : 'W';
                isBlack = !isBlack;
            }
        }

        int result = Integer.MAX_VALUE;
        for (int i = 0; i <= N - BOARD_SIZE; i++) {
            for (int j = 0; j <= M - BOARD_SIZE; j++) {
                int blackCount = 0;
                int whiteCount = 0;
                for (int k = 0; k < BOARD_SIZE; k++) {
                    for (int l = 0; l < BOARD_SIZE; l++) {

                        if (board[i + k][j + l] != whiteChessBoard[k][l]) {
                            whiteCount++;
                        }

                        if (board[i + k][j + l] != blackChessBoard[k][l]) {
                            blackCount++;
                        }
                    }
                }
                result = Math.min(result, Math.min(whiteCount, blackCount));
            }
        }

        System.out.println(result);

    }
}