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

백준 1018

문제 이해

N x M 으로 되어있는 정사각형에서 체스판 8 x 8을 만들려고 한다. 체스판은 흰색과 검은색이 번갈아서 칠해져야 한다. N x M → 8 x 8 만들 때 가장 적게 칠하는 칸 수를 구하면 된다.

문제 풀이

1. BufferedReader로 입력 받음
2. ans(정답)을 64로 초기화 (8x8이니까 최대 칠할 칸수는 64임. 사실은 32이지만 64로 일단 초기화)
3. 한칸씩 옮겨가며 8x8을 탐색한다.
4. 탐색할 때 열+행이 짝수면 W, 홀수면 B로 고정시킨다.
   • 지그재그로 색칠할 때 W인 것의 열+행이 짝수면 B인 것의 열+행은 홀수다.
   • 짝수면 W, 홀수면 B로 고정시켜서 다시 칠해야하는 칸수를 paint라고 하자.
     그렇다면, 짝수B, 홀수W로 고정시켜서 칠해야하는 칸수는 64-paint이다.
5. 제일 적은 paint 값을 구하여 답을 찾는다.
   
   

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		
		//입력받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		
		StringTokenizer st = new StringTokenizer(s);
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		char[][] square = new char[N][M];
		for(int i=0;i<N;i++) {
			square[i] = br.readLine().toCharArray();
		}
		
		//정답 구하기
		int ans = 64;
		
		for(int i = 0; i <= N - 8; i++) {
			for(int j = 0; j <= M-8; j++) {
				//해당i,j부터 8*8 탐색
				int paint=0; //칠해야할 칸 수 -> 짝수 W, 홀수 B로 고정하고 계산 
				for(int n=0;n<8;n++) {
					for(int m=0;m<8;m++) {
						if((n+m)%2==0) {
							if(square[i+n][j+m]!='W') paint++;
						}else {
							if(square[i+n][j+m]!='B') paint++;
						}
					}
				}
				paint = paint<32 ? paint : 64-paint; //칠해야할 칸 수는 paint 또는 64-paint
				ans = ans<paint ? ans : paint;
				
			}
		}
		System.out.println(ans);
		
		br.close();
	}

}