체스판 다시 칠하기


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

문제보기
Alt text

풀이

첫 번째칸이 흰색으로 시작되는 경우와 검은색으로 시작되는 경우 2가지가 있음을 주의!

소스코드

import java.util.Scanner;

public class Main {
	static boolean[][] map;
	static int min = 64;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		map = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			String str = sc.next();
			for (int j = 0; j < M; j++) {
				char c = str.charAt(j);
				if(c=='W')	//흰색이면 true
					map[i][j] = true;
				else	//검은색이면 false
					map[i][j] = false;
 			}
		}

		int row = N-7;
		int col = M-7;
		
		for(int i=0; i<row; i++) {
			for(int j=0; j<col; j++) {
				find(i, j);
			}
		}
		System.out.println(min);
	}
	public static void find(int i, int j) {
		int i_end = i + 7;
		int j_end = j + 7;
		boolean check = map[i][j];
		int cnt = 0;
		
		for(int ii = i; ii<=i_end; ii++) {
			for(int jj = j; jj<=j_end; jj++) {
				if(map[ii][jj] != check) {
					cnt++;
				}
				check = !check;	//다음 칸은 색을 바꿔야 함
			}
			check = !check;	//한 행이 끝나면 색을 한번 더 바꿔줌
		}
		
		//첫번째 칸과 반대되는 색으로 할때 색칠해야하는 개수는 (64-cnt)
		cnt = Math.min(cnt, 64-cnt);
		
		min = Math.min(cnt, min);
	}
}