[백준 알고리즘][자바] 1018번 : 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

 

브루트 포스의 문제입니다.

브루트 포스는 모든 경우의 수를 검사한다는 부분은 간단하지만, 어떤 경우의 수를 검사하는지가 어려운 거 같습니다.

 

문제 속에 힌트가 있었습니다.

8x8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다.

 

8x8 크기의 체스판으로 잘라낼 때, 잘라낼 8x8의 첫 시작 정사각형을 기준으로 살펴보면 규칙이 눈에 보입니다.

예제 입력을 보면서 8x8 크기의 체스판으로 잘라낼 수 있는 경우의 수를 살펴보겠습니다.

N = 8, M = 8 일 때는 8x8이 가능한 첫 시작 정사각형은 (1, 1)입니다.

N = 10, M = 10 일 때는 8x8이 가능한 첫 시작 정사각형은 (1,1) (2,1) (3,1) (1,2) (2,2) (3,2) (1,3) (2,3) (3,3)입니다.

N = 11, M = 12 일 때는 (1,1) (2,1) (3,1) (4,1).... (1,5) (2,5) (3,5) (4,5)입니다.

규칙이 눈에 보이시나요?

• N = 8, M = 8 일 때는 (1,1)
• N = 10, M = 10 일때는 (1,1)부터 (3,3)까지
• N = 11, M = 12 일 때는 (1,1)부터 (4,5)까지
• N = a, M = b 일 때는 (1,1)부터 (a-7, b-7)까지

따라서 경우의 수는 (가로 칸의 개수 - 7) X (세로 칸의 개수 -7)입니다.

여기서 첫 칸의 색깔이 흰색인 경우와 검은색인 경우가 존재합니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String NM_str = br.readLine();
		int N = Integer.parseInt(NM_str.split(" ")[0]);
		int M = Integer.parseInt(NM_str.split(" ")[1]);
		
		String[][] arr = new String[N][M];
		
		// 배열로 보드를 저장
		for(int i = 0 ; i < N ; i++) {
			String str = br.readLine();
			
			for(int j = 0 ; j < M ; j++) {
				if(str.charAt(j) == 'W') {
					arr[i][j] = "W";
				}else {
					arr[i][j] = "B";
				}
			}
		}
		
		int min = 64;
		
		for(int i = 0 ; i < N - 7 ; i++) { // 세로의 경우의 수
			for(int j = 0 ; j < M - 7 ; j++) { // 가로의 경우의 수 
				min = Math.min(min, cal(i, j, arr)); // 최소값을 저장
			}
		}
		
		bw.write(String.valueOf(min));
	
		br.close();
		bw.flush();
		bw.close();
	}
	
	public static int cal(int x, int y, String[][] WB) {
		
		int count = 0;
		
		String color = "W"; // 첫번째 칸을 W를 기준으로 색칠
		
		for(int i = x ; i < x + 8 ; i++) { // 시작컬럼부터 8개까지
			for(int j = y ; j < y + 8 ; j++) { //시작컬럼부터 8개까지
				
				// color는 정상적인 체스판이고 WB[i][j]와 비교
				if(!WB[i][j].equals(color)) {
					count++;
				}
				
				if(color.equals("W")) { // 컬러 변경
					color = "B";
				}else {
					color = "W";
				}
			}
			
			if(color.equals("W")) { // 줄이 바뀌면 바로 윗칸과 색깔이 달라야 함
				color = "B";
			}else {
				color = "W";
			}
		}
		
		count = Math.min(count, 64 - count);
		
		return count;
		
	}
}