[백준 온라인저지]체스판 다시 칠하기 - 브루트포스(4)

체스판 다시 칠하기

이번 포스팅 문제는 1018번 문제입니다. 이 문제 역시 브루트포스 알고리즘으로 풀이했습니다.

문제요약

M*N 단위 정사각형으로 이루어진 보드가 있을 때 8X8 체스판 모양으로 잘라서 다시 색칠하려고 합니다.  이때 체스판 모양을 만들기위해 다시 색칠해야 하는 정사각형의 최소 개수를 구하는 문제입니다.

풀이전략

1. 좌상단을 기준으로 체스판 크기만큼 잘라낸다. 

2. 잘라낸 체스판의 좌상단이 흰색일 때 다시 칠해야하는 개수를 구한다

3. 잘라낸 체스판의 좌상단이 검은색일 때 다시 칠해야하는 개수를 구한다

4. (2), (3)번의 값을 최소값으로 저장한다.

5. 보드 좌표를 이동하여 반복한다

구현하기

package BackJoon.브루트포스;
 
import java.util.Scanner;
 
public class _1018_체스판다시칠하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int height = sc.nextInt();
        int width = sc.nextInt();
        
        char[][] board = new char[height][width];
        for(int h=0; h<height; h++) {
            String row = sc.next();
            board[h] = row.toCharArray();
        }
        
        int min = 64;
        for(int h=0; h<height-7; h++) {
            for(int w=0; w<width-7; w++) {
                int changeCount = getChangeCount(board, h, w, h+7, w+7);
                if(changeCount < min) {
                    min = changeCount;
                }
            }
        }
        System.out.println(min);
    }
    
    private static int getChangeCount(char[][] board, int h1, int w1, int h2, int w2) {
        int count = 0;
        // 8X8 모양으로 체스판 생성
        char[][] chessBoard = new char[8][8];
        for(int h=0; h<8; h++) {
            for(int w=0; w<8; w++) {
                chessBoard[h][w] = board[h1+h][w1+w];
            }
        }
        // 새로만든 체스판을 순회하면서 바뀌어야하는 곳을 체크후 변경
        for(int h=0; h<8; h++) {
            // 세로줄이 같을 경우 변환이 필요
            if(h != 7 && (chessBoard[h][0] == chessBoard[h+1][0])) {
                chessBoard[h+1][0] = chessBoard[h][0] =='B'? 'W':'B';
                count ++;
            }
            // 가로줄이 같을 경우 변환이 필요
            for(int w=0; w<8-1; w++) {
                char c1 = chessBoard[h][w];
                char c2 = chessBoard[h][w+1];
                if(c1 == c2) {
                    count ++;
                    chessBoard[h][w+1] = c1=='B'? 'W':'B';
                }
            }
        }
        // 체스판의 좌상단이 흰색의 경우 n개 바꿔야한다면 검은색의 경우는 64-n개를 바꿔야 정상적인 체스판이 완성됨
        if(count <= 32) {
            return count;
        } else {
            return 64-count;
        }
    }
}
 

배운점

제가 생각하는 위 문제의 핵심은 아래와 같습니다. 

• 모든 경우의 수 구하기(board 에서 만들수있는 8x8 체스판)
• 각 체스판에서 색을 변화해야 하는 횟수 구하기

두 번째 핵심 로직을 개선하면 속도도 좀 더 나올 것 같네요.. 

1차원 배열로 풀어보려다가 더 복잡해질 것 같아서 그냥 2차원 배열로 풀이했습니다.