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

백준 1018번 문제 - 체스판 다시 칠하기

1018번: 체스판 다시 칠하기

---

문제 분석

 

 

• NxM보드에 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다.
• 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
• 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 
• 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

---

 

해결 키 포인트

 

• 완전 탐색
• 시작 위치를 0,0 부터 N-8, M-8 번까지 8x8 체스를 만들 수 있는 모든 경우의 수를 탐색
• 시작 블록이 검은색일지 흰색일지 정해지지 않았으므로, 두 경우 다 확인 
  • 더 작은 수를 시작위치(i,j)일 때 다시 칠하는 정사각형의 최소 개수
• 각 줄에 첫번째 위치인 블록일 경우, 위 블록과 다른 색으로 설정 
• 각 줄에 첫번째 위치가 아닌 블록일 경우, 왼쪽 블록과 다른 색으로 설정

---

코드

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static int [][] chess;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        chess = new int [N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                if (s.charAt(j) == 'W')
                    chess[i][j] = 0;
                else
                    chess[i][j] = 1;
            }
        }

        int min = 9999999;
        for (int i = 0; i <= N-8; i++) {
            for (int j = 0; j <= M-8; j++) {
                min = Math.min(min, getChangeCount(i,j));
            }
        }

        System.out.println(min);

        bw.flush();
        bw.close();
    }

    public static int getChangeCount(int x, int y) {
        int countW = 0;
        int countB = 0;

        int [][] chessW = new int[8][8];
        int [][] chessB = new int[8][8];

        for (int i = x; i < x+8; i++) {
            for (int j = y; j < y+8; j++) {
                if(i==x && j==y) {
                    chessB[i-x][j-y] = 1;
                    chessW[i-x][j-y] = 0;
                }
                else {
                    int getX = i-x;
                    int getY = j-y-1;
                    if (j==y) {
                        getX = i-x-1;
                        getY = j-y;
                    }

                    chessB[i-x][j-y] = (chessB[getX][getY] + 1)%2;
                    chessW[i-x][j-y] = (chessW[getX][getY] + 1)%2;
                }

                if(chessB[i-x][j-y] != chess[i][j]) {
                    countB++;
                }
                if(chessW[i-x][j-y] != chess[i][j]) {
                    countW++;
                }
            }
        }

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