[Java] 백준 #1018 (브루트 포스)

📍 출처

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

📝 문제

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

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

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

⌨️ 입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

🖨 출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

⌨️ 예제 입력 1

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

🖨 예제 출력 1

1

⌨️ 예제 입력 2

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

🖨 예제 출력 2

12

📚 내가 제출한 코드

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

public class App {

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

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

        Boolean arr[][] = new Boolean[N][M];

        // M x N 입력받음, true = W false = B
        for(int i = 0 ; i < N ; i++){
            String str = br.readLine();
            for(int j = 0 ; j < M ; j++){

                if(str.charAt(j) == 'W')
                    arr[i][j] = true;
                else{
                    arr[i][j] = false;
                }
            }
        }

        //y : 열 비교 횟수
        int start_y = N - 7;
        //x : 행 비교 횟수
        int start_x = M - 7;

        for(int i = 0 ; i < start_y ; i++){
            for(int j = 0 ; j < start_x ; j++){
                find(arr, i, j);
            }
        }

        System.out.println(min);
    }

    static void find(Boolean arr[][], int y, int x){
        int end_y = y + 8;
        int end_x = x + 8;
        int cnt = 0;

        //체스판 B, W 비교값
        boolean TF = arr[y][x]; // 첫 번째 칸의 색 

        for(int i = y ; i < end_y ; i++){
            for(int j = x ; j < end_x ; j++){
                // 올바른 색이 아닐경우 count 1 증가 
                if(arr[i][j] != TF){
                    cnt++;
                }
                /* 
				 * 다음 칸은 색이 바뀌므로
				 * true라면 false로, false 라면 true 로
				 * 값을 변경한다.
				 */
                TF = !TF;
            }
            TF = !TF;
        }

        /*
		 *  첫 번째 칸을 기준으로 할 때의 색칠 할 개수(count)와
		 *  첫 번째 칸의 색의 반대되는 색을 기준으로 할 때의
		 *  색칠 할 개수(64 - count) 중 최솟값을 count 에 저장 
		 */
        cnt = Math.min(64 - cnt, cnt);

        /*
		 * 이전까지의 경우 중 최솟값보다 현재 count 값이
		 * 더 작을 경우 최솟값을 갱신 
		 */
        min = Math.min(min, cnt);
    }
}

✏️ 내가 제출한 코드에 대한 설명

• W, B만 입력받으면 되므로 입력받을 2차원 배열의 자료형을 boolean형으로 해줌

• 8, 8 입력받으면 1번만 비교하면 되고 10, 12 입력 받으면 3 * 5 = 15 만큼 비교해야함 즉 반복문의 조건은

• 입력받은 수 - 7 를 해줘 2중 for문을 해줘야함

• 비교는 이전값과 다음값이 같으면 +1을 해주며 첫번째가 W일때와 B일때 두가지 경우가 나온다. 이 경우 하나의 값을 구해준다음 그 값에서 - 64를 해주면 다른 하나의 값이 구해짐 두 개중 더 작은 값을 선정

• 지금까지 구한 최소값과 지금 구한 최소값을 비교하여 더 작은값을 선정

• 모든 반복문이 돌았을 때 남아있는 값이 최소값임