[백준] 1018번 : 체스판 다시 칠하기 _ JAVA ( 주석 설명 )

1번

→ 입력받은 M*N 체스판에서 8*8 공간만큼의 경우를 전수 조사해서 정상 체스판과 다른 부분 개수 찾기

8*8 공간이 겹치는 부분의 중복 계산을 피하는 방법이 있을까.. 하며 시간을 잡아먹었던 문제

(브루트포스 문제답게 완전 탐색으로 해결)

 

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

public class Main {
    static int min = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //버퍼에서 데이터를 읽어오는 방식으로 속도가 빠르다.
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken()); //체스판 행의 수
        int N = Integer.parseInt(st.nextToken()); //체스판 열의 수

        char[][] input = new char[M][N];
        for(int i=0;i<M;++i){
            input[i] = br.readLine().toCharArray(); //개행마다 문자 배열로 바꿔, 행으로 바로 넣어주도록 한다.
        }


        //8*8 크기를 지정하는데 그 크기는 +8을 했을 때 M*N 까지여야 한다. (0 인덱스 시작이므로)
        for(int row=0;row+8<=M;++row){
            for(int column=0;column+8<=N;++column){
                find(input,row,column); //다시 칠해야 하는 정사각형의 최소 개수를 구하는 함수를 실행한다.
            }
        }

        System.out.println(min); //다시 칠해야 하는 정사각형의 최소값을 출력한다.
    }
    private static void find(char[][] input, int row, int column) {
        char block = input[row][column]; //시작점 위치를 할당해주었다. //'B' ,'W' 로 할당해주어도 상관없다.

        int count = 0;
        for (int i = row; i < row + 8; ++i) {
            for (int j = column; j < column + 8; ++j) {
                if (input[i][j] != block) {
                    ++count; //정상 체스판과 다르다면 카운팅 해준다.
                }

                block = block == 'B' ? 'W' : 'B'; //색깔 바꿔주기
            }

            block = block == 'B' ? 'W' : 'B'; //8*8 배열만 생각하면 된다, (홀수*홀수 배열은 고려 x)
        }

        count = Math.min(count, 64-count); //체스판이 W,B 두가지 경우의 수로 시작할 수 있으니, 두 경우를 모두 고려해서 count, 64-count 중 최소값을 할당한다.

        min = Math.min(min,count); //기존 최소값과 비교해서 갱신해준다.
    }
}