[백준] 자바 1018 체스판 다시 칠하기

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

---

테스트 케이스

 

입력 1

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

출력 1

1

 

입력 2

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

출력 2

12

 

입력 3

8 8
BBWBWBWB
BWBWBWBW
BWBWBWBW
BWBWBWBW
WBWBWBWB
WBWBWBWB
BWBWBWBW
BWBWBWBW

출력 3

25

---

접근

1. 숫자 두 개를 입력받습니다.(하나는 가로 하나는 세로)

 

2. 위에서 입력받은 숫자만큼 B, W를 입력받습니다(가로 * 세로만큼)

 

3. 저 같은 경우 B는 0으로 W는 1로 초기화해서 2차원 배열에 넣어줬습니다.

 

4. 받은 가로세로판에서 8*8 체스판을 만드는데 최소한의 수정으로 체스판을 만드는 게 이 문제의 핵심입니다.

 

5. 8*8 체스판은 경우의 수가 하나지만 8*9 체스판은 8*8 체스판이 2개 나오므로 경우의 수가 2개가 됩니다. 마찬가지로 가로, 세로 숫자가 커질때마다 경우의수가 늘어나게 됩니다. 결국 경우의 수는 (N-7) * (N-7)이 됩니다.

 

6. 함수를 통하여 (N-7) * (N-7) 번 반복하며 문자 하나하나 검사하면서 바꿔야 될 문자를 체크해줍니다.

(지금 체크한 것은 처음 색깔을 기준으로 바꿔야될 문자이며, 처음색깔을 바꾸고 시작하는 경우는 64-COUNT를 하면 나오게 됩니다. 이 둘값중 작은 값을 변수에 넣어 이용합니다.)

(EX) BBWBW에서 처음 값을 유지하고 하는 경우 4번의 색을 바꿔야 하지만, 첫 번째 색을 바꾸면 1번만 바꾸면 됩니다.

이를 계산하는 법은 총 개수(여기선 5) 5-4=1 이렇게 됩니다.

 

7. 위에서 계산한 최솟값을 전역 변수 최솟값에 넣어 위에서 따져본 (N-7) * (N-7) 번 경우의 수를 반복하여 최종 최솟값을 찾아냅니다.

 

이 문제를 풀면서 가장 중요한 것은 6번에서 얘기한 두 가지 경우의 수가 있다는 것을 깨닫는 것 같습니다.

---

코드

import java.awt.desktop.SystemEventListener;
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	/*
 	 1018 problem
	*/
	static int arr[][];
	static int min=64;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int h = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		
		arr = new int[h][w];
		for(int i=0; i<h; i++) {
			String str = br.readLine();
			for(int j=0; j<w; j++) {
				if(str.charAt(j)=='B')
					arr[i][j] = 0;
				else {
					arr[i][j] = 1;
				}
			}
		}
		for(int i=0; i<h-7; i++) {
			for(int j=0; j<w-7; j++) {
				find(i,j);
			}
		}
		bw.write(String.valueOf(min));
		bw.flush();
		br.close();
		bw.close();
	}
	static void find(int a,int b) {
		int count = 0;
		int com = arr[a][b];
		
		for(int i=a; i<a+8; i++) {
			for(int j=b; j<b+8; j++) {
				if(arr[i][j] !=com) {
					count++;
				}
					if(com==0) {
						com=1;
					}
					else {
						com=0;
					}
			}
			if(com==0) {
				com=1;
			}
			else {
				com=0;
			}
		}
		count = Math.min(count, 64-count);
		min = Math.min(count, min);
	}
}

---

주의