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

1018번: 체스판 다시 칠하기

 

해당 문제는 N * M 행렬이 주어졌을 때, 8 * 8 정사각형으로 잘랐을 때, 자른 정사각형들 영역 중에, 가장 최소로 칸을 색칠하는 값을 구해야 하는 문제입니다.

 

row : N / col : M 으로 했을 때 아래와 같이 체스판을 그릴 수가 있습니다. board[N][M]

 

8 * 8 의 정사각형으로 잘랐을 때, 나올 수 있는 정사각형 모양의 체스판 중 가장 다시 칠해야 하는 최솟값을 찾으면 됩니다.

 

[0][0] 자리에 B 또는 W 색이 올 수 있기 때문에 경우의 수가 2입니다.

그리고 사각형으로 잘랐을 때, 나올 수 있는 정사각형(체스판)의 개수입니다. (M - 7) * (N - 7) 

그리고 자른 정사각형의 첫 시작점의 row와 col을 구하는 공식은 

첫 번째 지점 row = N - 7

첫번째 지점 col = M - 7 

이고, 자른 정사각형의 마지막 row와 col 구하는 공식은 (정사각형의 8 * 8 ) 

마지막 지점 row = (첫 번째 지점 row) + 8;

마지막 지점 col = (첫번째 지점 col) + 8; 

 

위와 같은 공식을 가지로 비교를 하는 코드를 짜봤습니다.

 

package main;

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

public class Main1018 {
	
	private static char[][] board;
	private static int min = 64;
	private static final int BOARD_SIZE = 7;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		// 1. 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		board = new char[N][M];
		
		for(int i = 0; i < N; i++){
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for(int j = 0; j < M; j++) {
				board[i][j] = str.charAt(j);
			}
		}
		
		// 8 * 8 정사각형으로 자른 첫 위치
		int boardRow = N - BOARD_SIZE;
		int boardCol = M - BOARD_SIZE;
		
		for(int i = 0; i < boardRow; i++) {
			for(int j = 0; j < boardCol; j++) {
				getCountReDrawRectangle(i, j);
			}
		}
		
		System.out.println(min);
	}
	
	private static void getCountReDrawRectangle(int x, int y) {
		
		//자른 정사각형(8*8)의 끝 자리
		int end_x = x + 8;
		int end_y = y + 8;
		
		//자른 정사각형(8*8)의 맨 첫번째 줄 첫번째 칸의 색깔
		char pointColor = board[x][y];
		
		//새로 칠해야할 체스 칸의 수
		int count = 0;
	
		for(int i = x; i < end_x; i++) {
			for(int j = y; j < end_y; j++) {
				
				if(board[i][j] != pointColor) {
					count++;
				}
				
				//검증기준 색깔 변환 ( next Col )
				pointColor = convertColor(pointColor);
				
			}
			//검증기준 색깔 변환 ( next Row )
			pointColor = convertColor(pointColor);
			
		}
		
		//기준을 만약 W 로 했을 때,
		//첫번째 색깔이 W인 경우에서 비교를 시작했을 때와 
		//B인 경우에서 비교를 시작했을 때 새로 색칠해야할 갯수 중 가장 최소인 값으로 변경
		count = Math.min(count, 64 - count);
		
		//최대 경우의수 64 색칠갯수와 계산 된 색칠 갯수의 최소값 구하기
		min = Math.min(min, count);
		
	}
	
	private static char convertColor(char color) {
		
		return color == 'W' ? 'B' : 'W';
	}
	

}

 

요즘 알고리즘을 풀어야겠다는 생각이 들어 풀어보는데 코드를 짜기 전 확실히 문제를 먼저 이해해야하는 능력부터 길러야 할 것 같습니다.