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

문제

 

풀이

import java.util.Scanner;

public class Main {
    
	private final static char WHITE = 'W';
	private final static char BLACK = 'B';
	private final static char[][] CORRECT_BOARD_BLACK = new char[][] {
		{BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE},
		{WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK},
		{BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE},
		{WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK},
		{BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE},
		{WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK},
		{BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE},
		{WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK}
	};
	
	private final static char[][] CORRECT_BOARD_WHITE = new char[][] {
		{WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK},
		{BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE},
		{WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK},
		{BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE},
		{WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK},
		{BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE},
		{WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK},
		{BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE}
	};
	
    public static void main(String[] args) {
    	Scanner scanner = new Scanner(System.in);
    	
    	// 체스판 생성
    	int width = scanner.nextInt();
    	int height = scanner.nextInt();
    	
    	char[][] board = new char[width][height];
    	
    	for (int i = 0; i < width; i++) {
    		String colors = scanner.next();
			for (int j = 0; j < height; j++) {
				board[i][j] = colors.charAt(j);
    		}
    	}
    	
    	scanner.close();
    	
    	// 체스판에서 8x8을 선택한 후, 다시 칠해야 하는 정사각형의 최소 개수
    	int minimumChangedCount = -1;
    	
    	// 체스판 임의의 지점에서 8x8을 선택한다.
    	// 8x8보다 짧을 경우, break 한다.
    	for (int i = 0; i < board.length; i++) {
    		if (width - i < 8) break;
    		for (int j = 0; j < board[i].length; j++) {
    			if (height - j < 8) break;
    			
    			// 선택한 8x8 체스판에서 다시 칠해야 하는 정사각형의 개수를 구한다.
    			int changedCount = getColorChangedCount(board, i, j);
    			// 여태까지 구했던 정사각형의 개수 중 최소 개수를 구한다.
    			if (minimumChangedCount == -1 || changedCount < minimumChangedCount) minimumChangedCount = changedCount;
    		}
    	}
    	
    	System.out.println(minimumChangedCount);
    }
    
    // 체스판에서 임의의 x,y에서 시작하여 8x8 체스판을 뽑는다.
    // 이후 검정으로 시작하는 정상체스판, 흰색으로 시작하는 정상 체스판과 비교하여 다시 칠해야하는 정사각형의 개수를 구한다.
    // 둘중 작은 변경횟수를 리턴한다.
    public static int getColorChangedCount(char[][] board, int startX, int startY) {
    	int colorChangedCountBlack = 0;
    	int colorChangedCountWhite = 0;
    	for (int i = startX; i < startX + 8; i++) {
    		for (int j = startY; j < startY + 8; j++) {
    			if (board[i][j] != CORRECT_BOARD_BLACK[i - startX][j - startY]) colorChangedCountBlack++;
    		}
    	}
    	
    	for (int i = startX; i < startX + 8; i++) {
    		for (int j = startY; j < startY + 8; j++) {
    			if (board[i][j] != CORRECT_BOARD_WHITE[i - startX][j - startY]) colorChangedCountWhite++;
    		}
    	}
    	return colorChangedCountWhite > colorChangedCountBlack ? colorChangedCountBlack : colorChangedCountWhite;
    }
}

• 브루트포스 문제, 크기가 랜덤한 체스판에서 모든 8x8 경우를 추출하여, 그 중 정사각형을 다시 칠해야 하는 횟수를 구한다.
• getColorChangedCount() 함수에서, 비교연산이 복잡하면 시간초과가 발생할 수 있다.
• 그렇기 때문에 static final 변수로 올바른 체스판 2개(CORRECT_BOARD_BLACK, WHITE)를 미리 메모리에 생성해 놓고 비교하였다.

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