[백준] 1018번(Java)

📖 체스판 다시 칠하기

• [ 문제 ]
  지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
  
  체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
  
  보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

💡풀이

• W부터 시작하는 블록 "WBWBWBWB"과 B로 시작하는 블록 "BWBWBWBW"을 미리 설정해 놓고, M x N 보드판을 돌면서 교차로 블록을 비교해가면서 다른 부분을 체크한다.
• W 부터 시작하는 보드판과 B부터 시작하는 보드판 두 경우를 세서 최소값을 구한 뒤, 누적 계산된 최소값과 비교해서 최솟값을 다시 업데이트 한다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String[] wf = {"W", "B", "W", "B", "W", "B", "W", "B"};
        String[] bf = {"B", "W", "B", "W", "B", "W", "B", "W"};
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        String[][] tmp = new String[N][M];
        for(int i = 0 ; i < N ; i ++){
            tmp[i] = br.readLine().split("");
        }

        int ans = 64;

        for(int j = 0 ; j < N - 7; j ++ ){
            for(int k = 0 ; k < M - 7 ; k ++){
                // B로 시작 -> 몇 개?
                int bfirst = 0;
                for(int a = 0 ; a < 8 ; a ++){
                    for(int b = 0 ; b < 8; b ++){
                        if(a % 2 == 0){
                            if(!bf[b].equals(tmp[j + a][k + b])){
                                bfirst += 1;
                            }
                        } else {
                            if(!wf[b].equals(tmp[j + a][k + b])){
                                bfirst += 1;
                            }
                        }
                    }
                }
                int wfirst = 0;
                for(int a1 = 0 ; a1 < 8 ; a1 ++){
                    for(int b1 = 0 ; b1 < 8; b1 ++){
                        if(a1 % 2 == 0){
                            if(!wf[b1].equals(tmp[j + a1][k + b1])){
                                wfirst += 1;
                            }
                        } else {
                            if(!bf[b1].equals(tmp[j + a1][k + b1])){
                                wfirst += 1;
                            }
                        }
                    }
                }
                ans = Math.min(Math.min(wfirst, bfirst), ans);
            }
        }

        System.out.println(ans);
    }


}

백준 1018번 : https://www.acmicpc.net/submit/1018/88062254