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

< 문제 정보 >

[ 문제 ]

  검정과 흰색으로 이뤄진 N x M의 보드를 8 x 8의 체스판으로 만들고자 한다.
체스판은 흰색, 검은색, 흰색과 같이 서로 다른 색이 번갈아 칠해진 형태이기 때문에, 보드를 8 x 8로 자르고, 체스판의 형태가 되도록 색을 칠할 것이다. 이 때 체스판을 얻기 위해 최소 몇 번의 색칠이 이뤄져야하는지를 구하는 문제이다.

[ 예시 ]

• 입력

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

• 출력
  1
  ※ 중간에 위치한 BBB를 BWB로 만들기 위한 1번의 색칠을 통해 8 x 8 체스판을 만들 수 있다.

[ 규칙 ]

• 가로(N), 세로(M)은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다.
• B는 검은색, W는 흰색을 의미한다.

[ 백준 ]

• 브루트포스 알고리즘
• https://www.acmicpc.net/problem/1018

< 풀이 >

  본 문제에서 중요하게 생각할 것은 왼쪽 첫 번째가 흰색인 경우와 검은 색인 경우 2가지 모두 고려해야한다는 것이다. 둘 중 하나의 경우의 수를 구하고, 8 x 8로 이뤄진 체스판이기에 64 - 갯수를 하면, 반전됐을 경우의 결과값을 도출할 수 있다.

< 코드 >

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        start(bf);
    }
    private static void start(BufferedReader bf) {
        int[] length = getLength(bf);
        char[][] board = getBoard(length[0], length[1], bf);
        int result = calculate(board, length[0], length[1]);
        System.out.printf(String.valueOf(result));
    }
    private static int[] getLength(BufferedReader bf) {
        int[] length = new int[2];
        try {
            String s = bf.readLine();
            StringTokenizer st = new StringTokenizer(s);
            int width = Integer.parseInt(st.nextToken());
            int height = Integer.parseInt(st.nextToken());
            length[0] = width;
            length[1] = height;
        } catch (Exception e) {
            e.printStackTrace();
        }
        return length;
    }
    private static char[][] getBoard(int width, int height,BufferedReader bf) {
        char[][] board = new char[width][height];
        for(int i=0;i<width;i++){
            try {
                String s = bf.readLine();
                board[i] = s.toCharArray();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        return board;
    }
    private static int calculate(char[][] board, int width, int height) {
        int result = 64;
        for(int i=0;i<width-7;i++) {
            for (int j=0;j<height-7;j++) {
                int r = chess(board, i, j);
                result = Math.min(result, r);
            }
        }
        return result;
    }
    // board[n][m] means a starting point of a chess
    private static int chess(char[][] board, int n, int m) {
        char[][] cloneBoard = board.clone();
        int result=0;
        char start = cloneBoard[n][m];
        for (int i=n;i<n+8;i++) {
            for (int j=m;j<m+8;j++) {
                if (cloneBoard[i][j] != start)
                    result++;
                start = (start=='B')?'W':'B';
            }
            start = (start=='B')?'W':'B';
        }
        result = Math.min(result, 64-result);
        return result;
    }
}

내가 산정한 제한시간내로 풀지 못하여, 다른 분의 풀이를 참조하였다. 
true, false를 이용하여 문제 풀이를 하셨는데, 코드가 훨씬 간결하고, 이해하기도 쉬워 이런 관점에서도 문제를 풀 수 있구나하는 깨달음을 얻었다. 다시 한 번 푼 문제여도 다른 분들의 코드를 찾아볼 필요가 있음을 느꼈다.