[JAVA] 백준 1018 : 체스판 다시 칠하기

문제

NxM의 체스판이 주어졌을 때(8 <= N, M <= 20), 보드를 잘라 8x8의 체스판을 만들려고 한다. 이 때 체스판의 흰x백 배열을 만들기 위해 최소로 다시 색칠해야하는 칸의 개수를 구하는 문제.

접근방법

1. 체스판을 8x8씩 돌아가면서 다시 칠해야 하는 개수를 체크한다.

2. 체스판의 첫번째 칸 색에 따라 동일한 규칙을 적용받는 방법을 이용한다.

   즉, 첫번째 칸이 'W'일 경우에는 (배열이 0부터 시작한다고 하면, )짝수열의 짝수행은 W, 홀수행은 B가 되어야 하며, 홀수열의 짝수행은 B, 홀수행은 W가 되어야 한다.

3. 첫번째칸이 W인 경우와 B인 경우를 고려해 더 적은 수를 선택하여, 전체 중 가장 작은 수를 구한다. (처음에는 첫번째 칸의 색을 기준으로 비교를 했지만, 첫번째 칸을 다른 색으로 칠했을 때 더 조금만 칠해서 체스판을 만들 수 있는 경우가 있으므로, 첫번째 칸의 색에 관계 없이 모두 확인해 주어야 한다.)

소스코드

public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
​
    String input[] = in.readLine().split(" ");
    int N = Integer.parseInt(input[0]);
    int M = Integer.parseInt(input[1]);
​
    char[][] map = new char[N][M];
    for(int i=0; i<N; i++){
        String line = in.readLine();
        for(int j=0; j<M; j++)
            map[i][j] = line.charAt(j);
    }
​
    int min = 64;
    for(int i=0; i<N-8+1; i++){
        for(int j=0; j<M-8+1; j++){
​
            // B로 시작하는 체스판과 비교
            int diff_B = 0;
            for(int a=0; a<8; a++) {
                for (int b = 0; b < 8; b++) {
                    // B로 시작하면 짝수열(0,2..) - 짝수행 'B', 홀수행 'W'
                    //           홀수열(1,3..) - 짝수행 'W', 홀수행 'B'
                    if (a % 2 == 0) {
                        if (b % 2 == 0) {
                            if (map[i + a][j + b] != 'B')
                                ++diff_B;
                        } else {
                            if (map[i + a][j + b] != 'W')
                                ++diff_B;
                        }
                    } else {
                        if (b % 2 == 0) {
                            if (map[i + a][j + b] != 'W')
                                ++diff_B;
                        } else {
                            if (map[i + a][j + b] != 'B')
                                ++diff_B;
                        }
                    }
                }
            }
​
            // W로 시작하는 체스판과 비교
            int diff_W = 0;
            for(int a=0; a<8; a++)
                    for(int b=0; b<8; b++){
                        // W로 시작하면 짝수열(0,2..) - 짝수행 'W', 홀수행 'B'
                        //           홀수열(1,3..) - 짝수행 'B', 홀수행 'W'
                        if(a%2 == 0){
                            if(b%2 == 0){
                                if(map[i+a][j+b] != 'W')
                                    ++diff_W;
                            }else{
                                if(map[i+a][j+b] != 'B')
                                    ++diff_W;
                            }
                        }else{
                            if(b%2 == 0){
                                if(map[i+a][j+b] != 'B')
                                    ++diff_W;
                            }else{
                                if(map[i+a][j+b] != 'W')
                                    ++diff_W;
                            }
                        }
                    }
​
            // 최솟값 비교
            int dif_min = (diff_W < diff_B) ? diff_W : diff_B;
            if(dif_min < min)
                min = dif_min;
        }
    }
    System.out.println(min);
}