백준 1018번 체스판 다시 칠하기(Java)

정사각형으로 n*m으로 나눠지고 각 칸은 B,W중 하나로 칠해진 판을 체스판으로 만드려고 하는데, 이때 어느부분을 자르면 가장 적게 칠할수 있을지 푸는 문제. 구현은 쉬웠지만, 어떻게 구해야 할지 고민을 많이 했던 문제.

 

일단 8*8 체스판을 제작하려 했을때, 처음 시작하는 부분, 즉 배열로 따지면 (0,0)에 들어있는 색상에 따라 칠할수 있는 숫자가 달라진다. 색상에 따라 칠하는 수는 "64-색상에따른 칠하는 수"가 된다. 만약 B가 첫번째이면 W가 첫번째로 오는 체스판을 칠하는 수는 B의 수에다가 64를 빼면 된다. 그것만 알면 나머진 풀기 쉬운 문제.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int m=scanner.nextInt();
        int min=64;
        int compare_num=0;
        boolean[][] board=new boolean[n][m];
        
        //입력받은 문자열을 split하고 bool로 바꿈.
        for(int i=0;i<n;i++){
            String color=scanner.next();
            String[] color_list=color.split("");
            for(int j=0;j<m;j++){
                if(color_list[j].equals("W"))
                    board[i][j]=true;
                else
                    board[i][j]=false;
            }
        }
		//8*8을 주어진 배열에서 순서대로 탐색 및  칠해야 할 수 구하기
        for(int i=0;i<n-7;i++){
            for(int j=0;j<m-7;j++){
                int end_x=j+8;
                int end_y=i+8;
                boolean now=board[i][j];
                int count=0;
                for(int a=i;a<end_y;a++){
                    for(int b=j;b<end_x;b++){
                        if(now !=board[a][b])
                            count++;
                        now= !now;
                    }
                    now= !now;
                }
                //제일 작은 수 구하기
                compare_num=Math.min(count,64-count);
                min=Math.min(compare_num,min);
            }

        }
        System.out.println(min);
    }
}