BOJ 1018) 체스판 다시 칠하기

문제

 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

풀이

 8x8크기의 체스판에서 몇개의 정사각형을 다시 칠해야하는지 여부 : 8x8크기의 체스판의 종류는 두가지(검은색으로 시작 or 흰색으로 시작)이므로 두 가지 종류중에서 다른 칸이 작은 케이스를 다시 칠해야하는 정사각형의 최소 개수로 설정하면 된다. > 기준과 다른 칸의 개수와 (64-다른칸의개수)를 비교하여 작은것.

 MxN크기의 경우 (M-7)x(N-7)개 종류의 8x8 체스판을 선택할 수 있으므로 (M-7)x(N-7)번의 검사과정을 거쳐서 과정에서 나온 최소개수가 답이 된다. M과 N의 범위가 50이하이므로 복잡도에 문제가 없을것이라고 생각했음

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main practice = new Main();
        Scanner sc = new Scanner(System.in);
        String inputStr;
        int rst=64;
        int tmp=0;

        int n = sc.nextInt(); //세로:n
        int m = sc.nextInt(); //가로:m

        char[][] arr = new char[n][m];

        //arr에 input입력
        for(int i=0; i<n; i++) {
            inputStr = sc.next();
            for(int j=0; j<m; j++) {
                arr[i][j] = inputStr.charAt(j);
            }
        }

        //arr 검사
        for(int i=0; i<n-7; i++) {
            for(int j=0; j<m-7; j++) {
                tmp = needToChange(arr, i, j);
                if(rst>tmp)
                    rst = tmp;
            }
        }

        System.out.println(rst);

    }

    private static int needToChange (char[][] arr, int n, int m) {
        char[][] arrCompare = new char[8][8];
        int cnt=0;

        //체스판모양 샘플
        for(int i=0; i<8; i++) {
            for(int j=0; j<8; j++) {
                if((i%2==0)==(j%2==0))
                    arrCompare[i][j]='W';
                else
                    arrCompare[i][j]='B';
            }
        }

        //샘플과 arr 비교
        for(int i=0; i<8; i++) {
            for(int j=0; j<8; j++) {
                if(arr[i+n][j+m]!=arrCompare[i][j])
                    cnt++;
            }
        }

        return Math.min(cnt, 64 - cnt);
    }
}

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

1018번: 체스판 다시 칠하기