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

문제 링크

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

접근 방법

M,N의 크기에서 8*8로 정사각형을 탐색한다.

8*8 정사각형이 만들어지면 그 안에서 WBWBWB, BWBWBW로 시작하는 경우를 생각하여 일치하지 않는 사각형의 개수를 센다.

WBWBWB로 시작했으면 다음 행은 BWBWBW로 탐색해야 하기 때문에, 현재 행이 홀수인지 짝수인지에 따라서 어떤 순서와 비교해야 하는지 설정했다.

또한, 현재 카운트가 최소로 칠해야 하는 사각형의 수를 넘었다면 더이상 탐색할 필요가 없기 때문에 return했다.

코드

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

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

        int M = Integer.parseInt(tokens.nextToken()); //행
        int N = Integer.parseInt(tokens.nextToken()); //열

        char[][] map = new char[M][N];
        for (int i = 0; i < M; i++) {
            map[i] = br.readLine().toCharArray();
        }

        //8 * 8로 만들 수 있는 정사각형만큼 반복
        int row = M - 8 + 1;
        int col = N - 8 + 1;
        int res = Integer.MAX_VALUE;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                res = checkArea(i, j, map, res);
            }
        }
        System.out.println(res);

    }

    private static int checkArea(int row, int col, char[][] map, int res) {
        char[] W = {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'};
        char[] B = {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'};

        //현재 row행 col열에서 시작하여 8*8의 정사각형 확인
        int wcnt = 0; //W로 시작하는 경우 색칠할 사각형 수
        int bcnt = 0; //B로 시작하는 경우 색칠할 사각형 수

        //해당 정사각형에서 색이 일치하지 않는 사각형 개수 확인
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                char now = map[row + i][col + j];
                if(i%2==0){
                    if(now!=W[j]) wcnt++;
                    if(now!=B[j]) bcnt++;
                }else{
                    if(now!=B[j]) wcnt++;
                    if(now!=W[j]) bcnt++;
                }
                if(wcnt > res && bcnt > res)
                    return res;
            }
        }
        return Math.min(res, Math.min(wcnt, bcnt));
    }
}