[Java] 백준 1018번 - 체스판 다시 칠하기

문제 링크 : 백준 1018번 - 체스판 다시 칠하기 자바

 

N*M의 행렬이 주어졌을 때, 8*8의 크기로 잘라내어 최소한으로 다시 칠할 수 있도록 하는 문제이다.

예로, 10*10의 검정색 행렬이 주어졌을 때 위 사진처럼 초록, 주황, 파랑 등 여러 위치에서 8*8의 크기로 잘라낼 수 있고, 이는 (0~N-8, 0~M-8)을 기준점으로 하여 10*10 행렬의 모든 부분 8*8 행렬을 탐색할 수 있다.

- 0~(10-8), 0~(10-8)

=> 0, 0

=> 0, 1

=> 0, 2

=> 1, 0

=> 1, 1

=> 1, 2

=> 2, 0

=> 2, 1

=> 2, 2

 

그런 후 이 부분 행렬을 정답 행렬(correctMatrix1, correctMatrix2)과 비교하여 최소로 바꿀 수 있는 수가 몇인지 탐색하여 반환한다.

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

public class Main {
    static char[][] matrix;
    static char[][] correctMatrix1 =   {"BWBWBWBW".toCharArray(),
                                        "WBWBWBWB".toCharArray(),
                                        "BWBWBWBW".toCharArray(),
                                        "WBWBWBWB".toCharArray(),
                                        "BWBWBWBW".toCharArray(),
                                        "WBWBWBWB".toCharArray(),
                                        "BWBWBWBW".toCharArray(),
                                        "WBWBWBWB".toCharArray()};
    static char[][] correctMatrix2 =   {"WBWBWBWB".toCharArray(),
                                        "BWBWBWBW".toCharArray(),
                                        "WBWBWBWB".toCharArray(),
                                        "BWBWBWBW".toCharArray(),
                                        "WBWBWBWB".toCharArray(),
                                        "BWBWBWBW".toCharArray(),
                                        "WBWBWBWB".toCharArray(),
                                        "BWBWBWBW".toCharArray()};

    static int N;
    static int M;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        N = input[0];
        M = input[1];
        matrix = new char[N][M];
        for (int i = 0; i < N; i++) {
            matrix[i] = br.readLine().toCharArray();
        }
        int min = N * M;
        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                int result = getFillCount(i, j);
                if (result < min) min = result;
            }
        }
        System.out.println(min);


    }

    public static int getFillCount(int x, int y){
        int count1 = 0;
        int count2 = 0;
        for (int i = x; i < x + 8; i++) {
            for (int j = y; j < y + 8; j++) {
                if (matrix[i][j] != correctMatrix1[i-x][j-y]){
                    count1++;
                }
                if (matrix[i][j] != correctMatrix2[i-x][j-y]){
                    count2++;
                }
            }
        }
        if (count1 < count2)
            return count1;
        return count2;
    }
}