[BOJ] 1018 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

2022-06-19

---

import java.util.Scanner;
 
public class Main1018 {
    public static int N, M;
    public static char[][] arr;
    public static int solve(int sx, int sy) {
       char val = arr[sx][sy];
       int count = 0;
       boolean flag = false;
       for(int i = sx; i < sx+8; i++) {
           for(int j = sy; j < sy+8; j++) {
               if(arr[i][j] != val) count++;
               val = val == 'W' ? 'B' : 'W';
           }
           val = val == 'W' ? 'B' : 'W';
       }
       return Math.min(count, (64-count));
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
 
        arr = new char[N][M];
        int answer = Integer.MAX_VALUE;
 
        for(int i = 0; i < N; i++) {
            String str = sc.next();
            for(int j = 0; j < M; j++) {
                arr[i][j] = str.charAt(j);
            }
        }
        for(int i = 0; i <= N-8; i++) {
            for(int j = 0; j <= M-8; j++) {
                answer = Math.min(answer, solve(i, j));
            }
        }
        System.out.println(answer);
    }
}

# 문제풀이

 

체스판에서 8x8씩 떼어서 시작을 W / B로 했을 때, 다시 칠해야하는 체스판의 수를 계산하면 된다. 

 

1) 0 ~ (N-8), 0 ~ (M-8)까지 8x8이 되는 모든 경우의 수를 체크한다.

N-8, M-8을 한 이유는 길이가 8x8인 체스판이기 때문이다. 예를 들어 N이 10, M이 13면 N은 0, 1, 2까지 출발지점을 잡을 수 있고, M은 0, 1,2 ,3 ,4, 5에서 시작할 수 있다.

 

즉, (N-7)*(M-7) 만큼의 경우의 수를 계산한다. 

 

2) solve(sx, xy) 값을 넘겨서 예를 들어 B로 시작했으면 첫째줄은 BWBWBWBW, 그 다음줄은 WBWBWBWB 로 반복하면서 현재 칠해진 값이랑 비교를 했다. 다음 값을 넘어갈때마다 기준 값의 반대값 (B <-> W)으로 만들면서 비교했다. 

 

다음 줄로 아예 넘어갈 때는 시작점이 달라져서 한 번 더 반대값으로 바꾸고 비교했다. 

 

3) 처음 시작이 예를 들어 B였다면, B로 시작했을 때 칠해야하는 체스판의 수를 64(8x8)개에서 빼준 수와 B로 시작했을 때 칠해야하는 수 중 더 작은 값을 return 했다. 64 - B로 시작했을때 칠해야하는 체스판의 수는 W로 시작했을 때의 경우의 수와 같다.

 

그래서 결국엔 1)번 경우의 수에 (N-7)*(M-7) *2 를 한 경우가 최종 경우의 수가 된다.