[자바]백준 1018번 체스판 다시 칠하기[브루트포스][엄탱]

문제 링크

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

1018번: 체스판 다시 칠하기

문제 풀이

간단하게 설명해서 W와 B가 칠해져 있는 M x N 크기의 보드에서 8 x 8 크기로 잘라서 체스판을 만들려고 한다.

체스판은 W와 B가 교차해야 하는데 M x N 크기의 보드에서 8 x 8을 잘랐을 때 W와 B가 교차하는 체스판을 만들기 위해서 W 혹은 B를 다시 칠해야 하는 정사각형 개수의 최솟값을 구하는 문제이다.

 

예를 들어서, 9x9 크기의 보드에서는 8x8 크기를 4개를 만들 수 있고 8x8 크기의 보드판 4개에서 W와 B를 다시 칠해서 체스판을 만들때 최소로 변경하는 개수를 구하는 문제이다.

해설

해당 문제는 알고리즘 분류가 브루트 포스 알고리즘으로 모든 경우의 수를 탐색하면 된다.

그래도 제한시간 안에 할 수 있는지 파악해 보자

• 제한 시간: 2초
• 최대 경우의 수: 2,336,672 (43 * 43 *  8 * 8 * 2)

완전 탐색을 진행해도 충분한 시간이라고 생각한다.

완전 탐색을 하기 위해 모든 경우의 수를 생각 해보자

첫 번째! 0부터 N - 7행 전까지, 0부터 M - 7열 전까지 탐색 (43 * 43번)

8 * 8 보드의 개수를 따지는 것이다.

즉, 8 * 8 보드를 조각낼 수 있는 경우의 수이다.

두 번째! 처음 탐색 기준을 W로 할지 B로 할지 (2번)

처음 탐색 기준을 W로 할지 B로 할지도 필요한 것 같다고 생각한다.

예를 들어서 아래와 같은 경우에 처음 오는 문자로 기준으로 하면 최솟값이 나오지 않는다.

BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

위와 같은 경우에는 B로 잡고 시작하면 63이 나오고 W로 잡고 시작하면 1이 나온다. 

둘 다 검사를 해봐야 한다.

세 번째! 시작 점부터 8행 8열 전부 탐색 (8 * 8번)

본격적으로 8행 8열 총 64개를 전부 탐색하여 다시 칠해줘야 하는 정사각형을 카운트해주면 된다.

코드

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

public class Main {
    static int N;
    static int M;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        String[] arr = new String[N];

        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine();
        }

        System.out.println(count(arr));
        br.close();
    }

    public static int count(String[] arr) {
        int result = Integer.MAX_VALUE;

        for (int i = 0; i < N - 7; i++) {
            for (int j = 0; j < M - 7; j++) {
                for (int k = 0; k < 2; k++) {
                    char start = k == 0 ? 'W' : 'B';

                    int count = 0;
                    for (int n = i; n < i + 8; n++) {
                        for (int m = j; m < j + 8; m++) {
                            if (start != arr[n].charAt(m)) {
                                count++;
                            }

                            start = start == 'W' ? 'B' : 'W';

                        }

                        start = start == 'W' ? 'B' : 'W';
                    }
                    
                    result = Math.min(result, count);
                    
                    if (result == 0) {
                        return 0;
                    }
                }
            }
        }

        return result;
    }
}