boj 1018 체스판 다시 칠하기

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

브루트포스 문제로 8*8 크기씩 계속 비교해가며 다시 칠해야할 갯수의 최솟값을 구해야합니다.

 

cnt1 => 맨 왼쪽 위 칸이 B로 칠해질 경우

cnt2 => 맨 왼쪽 위 칸이 W로 칠해질 경우

 

cnt1의 경우에는 i가 짝수일 때 BWBWBWBW, 홀수일 때 WBWBWBWB를 만들어야 합니다.

cnt2의 경우에는 i가 짝수일 때 WBWBWBWB, 홀수일 때 BWBWBWBW를 만들어야 합니다.

 

각 인덱스에서 다른색이 칠해져있으면 해당cnt를 증가시켜줍니다.

이 과정을 8*8 크기만큼 반복하여 최솟값을 출력합니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char ch[][];
    static int N, M, ans = 2500;
 
    static void func(int x, int y) {
        int cnt1 = 0;
        int cnt2 = 0;
        for (int i = x; i < x + 8; i++) {
            for (int j = y; j < y + 8; j++) {
                if (i % 2 == 0) {
                    if (j % 2 == 0) {
                        if (ch[i][j] == 'B')
                            cnt2++;
                        else
                            cnt1++;
                    } else {
                        if (ch[i][j] == 'B')
                            cnt1++;
                        else
                            cnt2++;
                    }
                } else {
                    if (j % 2 == 0) {
                        if (ch[i][j] == 'B')
                            cnt1++;
                        else
                            cnt2++;
                    } else {
                        if (ch[i][j] == 'B')
                            cnt2++;
                        else
                            cnt1++;
                    }
                }
            }
        }
 
        ans = Math.min(ans, Math.min(cnt1, cnt2));
    }
 
    static void solve() {
        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                func(i, j);
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        ch = new char[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            ch[i] = st.nextToken().toCharArray();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        solve();
    }
}