자바(백준) 1018 체스판 다시 칠하기

오답 노트 & 새로 알게 된 점

이 문제는 규칙성이 중요하다.

 

제일 처음 시작한 문자가 B일 경우와 W일 경우 아래와 같은 규칙이 나타난다.

홀수 + 홀수 = 짝수

홀수 + 짝수 = 홀수

짝수 + 짝수 = 짝수

 

처음 시작 문자가 B일 때 생각해보자.

홀수일 경우에는 W가 와야하고, 짝수일 경우에 B가 와야한다.

그래서 i+j가 홀수인데 W가 아니면 cnt를 늘리고, i+j가 짝수인데 B가 아니면 cnt를 늘린다.

 

이 때, 처음 시작 문자가 W일 때와 반대이기 때문에

64 - cnt를 하면 W일 때를 구할 수 있다.

 

그래서 cnt와 64-cnt 중 최소값을 리턴하면 된다.

 

그리고 모든 행과 열을 탐색하면서 최솟값을 찾으면 된다.

 

---

코드

 

package BruteForce_Search;
 
import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M, ans = 64;
    static char A[][];
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        for (int i = 1; i + 7 <= N; i++) {
            for (int j = 1; j + 7 <= M; j++) {
                ans = Math.min(ans, search(i, j));
            }
        }
 
        System.out.println(ans);
    }
 
    static int search(int x, int y) {
        int cnt = 0;
        for (int i = x; i <= x + 7; i++) {
            for (int j = y; j <= y + 7; j++) {
                if ((i + j) % 2 == 0 && A[i][j] != 'B') {
                    cnt++;
                }
                if((i+j) % 2 == 1 && A[i][j] != 'W'){
                    cnt++;
                }
            }
        }
 
        return Math.min(cnt, 64-cnt);
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
 
        A = new char[N + 1][M + 1];
 
        for (int i = 1; i <= N; i++) {
            String s = br.readLine();
            for (int j = 1; j <= M; j++) {
                A[i][j] = s.charAt(j - 1);
            }
        }
    }
}