BOJ) 체스판 다시 칠하기

체스판 다시 칠하기

1018번: 체스판 다시 칠하기

풀이

 

흰색과 검은색이 랜덤하게 칠해진 n x m 크기의 보드가 주어지는데, 이 보드를 8x8로 잘라서 체스판으로 이용하는 경우 최소 책칠작업의 횟수를 구하는 문제다.

체스판은 흰색으로 시작하는 경우, 검은색으로 시작하는 경우 두 경우밖에 없기 때문에, 두 보드를 먼저 final로 선언했다.

 

for문을 돌면서 8x8로 보드판을 자르면서 검사했다.

보드의 시작점은 0~n-8 , 0 ~m-8 이 된다. (n = 보드의 y축 최대 값, m = 보드의 y축 최대 값)

각각 시작점으로 부터 8x8 체스판으로 잘라서 흰색으로 시작하는 체스판일 때, 재색칠해야하는 칸의 수와

검은색으로 시작하는 체스판일 때, 재색칠해야하는 칸의 수를 각각 저장하면서 탐색했다.

 

둘 중 더 작은 작업 수를 return하여 8x8로 자를 수 있는 모든 보드판을 검사하며 최소 값을 구했다.

 

코드

 

코드

 

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

public class Main {
    final static char[][] WHITE_BOARD = {{'W','B','W','B','W','B','W','B'},
                                        {'B','W','B','W','B','W','B','W'},
                                        {'W','B','W','B','W','B','W','B'},
                                        {'B','W','B','W','B','W','B','W'},
                                        {'W','B','W','B','W','B','W','B'},
                                        {'B','W','B','W','B','W','B','W'},
                                        {'W','B','W','B','W','B','W','B'},
                                        {'B','W','B','W','B','W','B','W'}};
    final static char[][] BALCK_BOARD = {{'B','W','B','W','B','W','B','W'},
                                        {'W','B','W','B','W','B','W','B'},
                                        {'B','W','B','W','B','W','B','W'},
                                        {'W','B','W','B','W','B','W','B'},
                                        {'B','W','B','W','B','W','B','W'},
                                        {'W','B','W','B','W','B','W','B'},
                                        {'B','W','B','W','B','W','B','W'},
                                        {'W','B','W','B','W','B','W','B'}};
    final static int MAX_LEN = 8;

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        char[][] board = new char[n][m];

        for(int i=0; i<n; i++) {
            board[i] = br.readLine().toCharArray();
        }
        br.close();
        solution(n,m,board);
    }

    private static void solution(int n, int m, char[][] board) {
        int answer = Integer.MAX_VALUE;

        for(int yStart=0; yStart<=n-MAX_LEN; yStart++) {
            for(int xStart=0; xStart<=m-MAX_LEN; xStart++) {
                answer = Math.min(answer, getColoring(board,yStart,xStart));
            }
        }
        System.out.println(answer);
    }

    private static int getColoring(char[][] board, int yStart, int xStart) {
        int white =0, black =0;
        int endX = xStart+MAX_LEN;
        int endY = yStart+MAX_LEN;
        for(int y=yStart; y<endY; y++) {
            for(int x=xStart; x<endX; x++) {
                if(board[y][x] != WHITE_BOARD[y-yStart][x-xStart]) {
                    white++;
                }
                if(board[y][x] != BALCK_BOARD[y-yStart][x-xStart]) {
                    black++;
                }
            }
        }
        return Math.min(white,black);
    }
}