[99클럽 코테 스터디 11일차 TIL / 백준] 1018 - 체스판 다시 칠하기 (브루트포스)

99클럽 코테스터디 11일차 TIL
KeyWord : 브루트포스

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

 

---

 

풀이

모든 경우의 수를 확인해 보아야 하는 브루트포스 문제다. 모든 경우의 수를 확인해보지 않으면 현재의 값이 최솟값임을 보장하지 못하기 때문이다.

브루트포스임을 아는데, 로직의 구현에서 실패를 하였다면 시작 부분의 색을 바꿀지, 바꾸지 않을지를 고려하지 않았기 때문일 것이다.

즉, 탐색을 진행할 때

1. 시작 부분의 색을 바꾸지 않고 탐색 진행
2. 시작 부분의 색을 바꾸고 탐색 진행

이 부분까지 고려하여 구현하면 된다.

 

하지만, 브루트포스의 핵심은 문제 해결에 필요한 로직을 얼마나 효율적으로 구현하는가에 달려있다. (물론 이 문제는 N과 M의 크기가 50 이하로 작기 때문에 아래의 아이디어를 떠올리지 못했더라도 통과할 수 있다.)

브루트포스 자체가 모든 경우의 수를 확인해야 하기에, 이 부분에서부터 많은 시간을 잡아먹게 된다. 그러므로 로직에 불필요한 반복이 추가되면 효율성 체크에서 실패할 수 있다.

여기서 더 코드를 효율적으로 바꿀 수 있는 부분을 생각해보자.

시작 부분이 흰색이었을 때 최솟값이 40이 나왔다는 것은 색이 변경된 부분이 40개라는 것이다. 반대로 생각하면 색이 변경되지 않은 부분이 26개가 되는 것은 당연하다.

그러면 똑같은 체스판에서 시작부분을 흰색에서 검정색으로 바꾸면서 탐색을 시작한다고 가정하자. 이 경우에는 색이 변경되는 정사각형이 26개, 색이 변경되지 않는 정사각형이 40개가 된다.

즉, 32개를 초과하여 색을 칠해야 하는 경우에는 시작점을 W → B 혹은 B → W로 바꾸는 것이 더 효율적이라는 것을 알 수 있다. (이해가 잘 가지 않는다면, 4x4 정도의 작은 체스판을 그려보면서 천천히 생각해보면 금방 이해가 될 것이다.)

if (result > 32)  
    result = 64 - result;  

따라서 탐색 후 구한 값이 32를 넘었을 경우에 이렇게 변경하는 코드를 추가하는 것만으로 반복 횟수를 절반으로 감소시킬 수 있다.

코드

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

public class Main {  
    static Character[][] board;  
    static int ans = 32;  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer stk = new StringTokenizer(br.readLine());  

        int n = Integer.parseInt(stk.nextToken());  
        int m = Integer.parseInt(stk.nextToken());  

        board = new Character[n][m];  
        for (int i = 0; i < n; i++) {  
            String line = br.readLine();  
            for (int j = 0; j < m; j++) {  
                board[i][j] = line.charAt(j);  
            }  
        }  

        for (int i = 0; i <= n - 8; i++) {  
            for (int j = 0; j <= m - 8; j++) {  
                solution(i, j);  
            }  
        }  

        System.out.println(ans);  
    }  

    private static void solution(int startX, int startY) {  
        // 현재 위치에서 오른쪽과 아래쪽만 확인하면 됨.  
        int[] dx = {0, 1};  
        int[] dy = {1, 0};  
        int result = 0;  

        // board 깊은 복사  
        int[][] copyBoard = new int[8][8];  
        for (int i = 0; i < 8; i++) {  
            for (int j = 0; j < 8 ; j++) {  
                copyBoard[i][j] = board[startX + i][startY + j] == 'W' ? 1 : -1;  
            }  
        }  

        for (int i = 0; i < 8; i++) {  
            for (int j = 0; j < 8; j++) {  

                for (int k = 0; k < 2; k++) {  
                    int nextX = i + dx[k];  
                    int nextY = j + dy[k];  

                    if (nextX >= 8 || nextY >= 8) {  
                        continue;  
                    }  

                    if(copyBoard[i][j] == copyBoard[nextX][nextY]) {  
                        result++;  
                        copyBoard[nextX][nextY] = copyBoard[i][j] * -1;  
                    }  
                }  

            }  
        }  
        if (result > 32)  
            result = 64 - result;  
        ans = Math.min(ans, result);  
    }  
}