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

---

무작위로 칠해져 있는 체스판에서, 가장 적게 색을 다시 칠할 수 있는 8x8 체스판을 오려낼 때의 다시 칠하는 수를 출력하는 문제이다.

 

나는 어떤 로직을 구상했냐면, 주어진 체스판에서 기준점을 잡는다. 이 기준점의 가로와 세로는 각각 0 ~ N-8, 0 ~ M-8까지의 범위를 가진다. (그 이상을 넘어가면 범위가 초과되므로 그 점을 기준으로 하는 8x8 체스판을 오려낼 수 없기 때문)

 

그리고 그 기준점을 모두 돌면서, 각 기준점 별로 오른쪽으로 8칸, 아래로 8칸을 잘라 다시 칠해야 하는 개수를 구한다.
이 때에도 기준점이 B인지 W인지 두 가지 경우의 수를 모두 따져 보아야 한다.

 

이렇게 작성하긴 했는데... 사실 이 간단한 문제 하나 가지고 1시간 30분을 고민했다...
브루트포스 왜이렇게 어렵지?? 모든 경우의 수를 다 따진다는 게 너무 복잡한 듯...

차라리 그리디나 DP가 더 쉬운 것 같기도...? ㅋㅋㅋㅋㅋ

 

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

public class ChessRepaint {

    static char[][] chess;

    public static int stoi(String st) {
        return Integer.parseInt(st);
    }

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


        int N = stoi(st.nextToken());
        int M = stoi(st.nextToken());
        chess = new char[N][M];

        // 체스판을 채운다.
        for (int i=0; i<N; i++) {
            String line =br.readLine();
            for (int j=0; j<M; j++) {
                chess[i][j] = line.charAt(j);
            }
        }

        // 기준점에서 아래로 +8, 오른쪽으로 +8 이동해야 하므로 가능한 영역만 선택.
        int min = Integer.MAX_VALUE;
        for (int i=0; i<N-7; i++) {
            for (int j=0; j<M-7; j++) {
                int count = blackOrwhite(i, j);
                min = Math.min(min, count);
            }
        }

        System.out.println(min);
    }


    public static int blackOrwhite(int x, int y) {

        // 첫 번째 수(기준점)가 B라고 가정하는 경우
        int countB = 0;
        for (int i=x; i<x+8; i++) {
            for (int j=y; j<y+8; j++) {
                if (i%2 == 0) { // 홀수 번 째 x (맨 앞자리가 B)
                    if (j%2 == 0) {
                        if (chess[i][j] == 'W') {
                            countB++;
                        }
                    } else {
                        if (chess[i][j] == 'B') {
                            countB++;
                        }
                    }
                } else { // 짝수 번 째 y (맨 앞자리가 W)
                    if (j%2 == 0) {
                        if (chess[i][j] == 'B') {
                            countB++;
                        }
                    } else {
                        if (chess[i][j] == 'W') {
                            countB++;
                        }
                    }
                }
            }
        }

        // 첫 번째 수(기준점)가 W라고 가정하는 경우
        int countW = 0;
        for (int i=x; i<x+8; i++) {
            for (int j=y; j<y+8; j++) {
                if (i%2 == 0) { // 홀수 번 째 x (맨 앞자리가 W)
                    if (j%2 == 0) {
                        if (chess[i][j] == 'B') {
                            countW++;
                        }
                    } else {
                        if (chess[i][j] == 'W') {
                            countW++;
                        }
                    }
                } else { // 짝수 번째 y (맨 앞자리가 B)
                    if (j%2 == 0) {
                        if (chess[i][j] == 'W') {
                            countW++;
                        }
                    } else {
                        if (chess[i][j] == 'B') {
                            countW++;
                        }
                    }
                }
            }
        }

        return Math.min(countB, countW);
    }
}