[백준]1018번 체스판 칠하기(JAVA)

0. 문제 링크

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

1018번: 체스판 다시 칠하기

 

1. 문제 설명

1) M*N 체스판을 잘라 각 칸을 검은색이나 흰색으로 번갈아 있는 8*8 체스판을 만들려고 함

2) 다시 칠해야 하는 정사각형 개수의 최소값 구하기

 

2. 입출력

// input
8 8 // M N
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

// output
1

 

3. 코드

import java.io.*;
import java.util.*;

public class b1018 {

	private static boolean[][] map;
	private static int ans;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int M = Integer.parseInt(st.nextToken()); // 가로
		int N = Integer.parseInt(st.nextToken()); // 세로
		map = new boolean[M][N]; // 체스판
		for (int i = 0; i < M; i++) {
			String s = br.readLine();
			for (int j = 0; j < N; j++) {
				if(s.charAt(j) == 'W') {
					map[i][j] = true;
				} else map[i][j] = false;
			}
		}

		ans = Integer.MAX_VALUE; 
		int temp = 0; // 다시 칠해야 하는 정사각형의 개수
		
		for (int i = 0; i <= M-8; i++) { // 8*8 체스판으로 잘라서 생각
			for (int j = 0; j <= N-8; j++) {
				
				// 기준점이 true
				temp = 0; 
				if(map[i][j] != true) temp++; // 기준점이 true가 아니면 칠하기
				find(i, j, true, temp); // 8*8 체스판 확인
				
				// 기준점이 false
				temp = 0;
				if(map[i][j] != false) temp++; // 기준점이 false가 아니면 칠하기
				find(i, j, false, temp); // 8*8 체스판 확인
				
			}
		}
		
		System.out.println(ans); // 출력
		
	}

	private static void find(int i, int j, boolean check, int temp) {
		for (int r = i; r < i+8; r++) {
			for (int c = j; c < j+8; c++) {
				
				if(r == i && c == j) continue; // 첫 칸은 패스
				
				else if(c == j) { // 다음 줄의 첫 칸
					if(check != map[r][c]) {
						temp++;
					}						
				}
				
				else if(check == map[r][c]) {
					temp++; // 정사각형 칠하기
					check = !map[r][c]; // 바꾸기						
				}
				
				else {
					check = map[r][c];
				}
				
			}
		}
		
		ans = Math.min(ans, temp); // 최소값 찾기
	}

}

 

실행 결과

 

4. 회고

1) 체스판에는 W(hite), B(lack) 두 가지 경우만 존재하므로 char보다는 boolean으로 만듦

- W가 아닐 때는 B, B가 아닐 때는 W로 상태를 쉽게 바꿀 수 있음

2) 8*8 체스판의 (0,0) 값을 기준으로 W, B 두 가지 경우를 모두 판단해야 함

3) (0,0) 첫 칸, (r, 0) 다른 줄의 첫 칸, 나머지 칸의 경우로 나누어서 다시 칠해야 하는지 판단

 

5. Github