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

찾아보면 쉬운 문제라고 많이들 하시지만,, 나는 매우 시간이 오래걸렸다.

 

1. 8 x 8 보드를 W기준, B기준으로 2가지 우선 그려놓는다.

2. 입력된 보드를 8x8만큼 범위를 지정하고 이동하며, 위에서 기 작성된 ref 보드와 비교한다.

    -> White / Black 일 때 각각 다른 부분을 count 한 후, 작은 수를 리턴한다.

3. 리턴 된 값을 이전 범위 지정 시 최소값과 계속 비교해가며 갱신한다.

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

public class Main {
    static int min_value = 64;

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

        int height = Integer.parseInt(st.nextToken());
        int width = Integer.parseInt(st.nextToken());

        boolean[][] inputBoard = new boolean[height][width];

        for (int i = 0; i < height; i++) {
            String str = br.readLine();
            for (int j = 0; j < width; j++) {
                if (str.charAt(j) == 'W') {
                    inputBoard[i][j] = true;
                } else
                    inputBoard[i][j] = false;
            }
        }
        int endPointX = width - 7;
        int endPointY = height - 7;

        for (int y = 0; y < endPointY; y++) {
            for (int x = 0; x < endPointX; x++) {
                min_value = Math.min(min_value, getMapping(x, y, inputBoard));
            }
        }
        System.out.println(min_value);
    }

    private static int getMapping(int x, int y, boolean[][] inputBoard) {
        int result = 0;
        boolean[][] wb = makeInitBoard("W");
        boolean[][] bb = makeInitBoard("B");
        int w_count = 0;
        int b_count = 0;

        for(int i=0; i<8; i++) {
            for(int j=0; j<8; j++) {
                if(wb[i][j] != inputBoard[y+i][x+j]) {
                    w_count ++;
                }
                if(bb[i][j] != inputBoard[y+i][x+j]) {
                    b_count ++;
                }
            }
            result = Math.min(w_count, b_count);
        }
        return result;
    }
    private static boolean[][] makeInitBoard(String color) {
        boolean[][] result = new boolean[8][8];

        boolean white = true;

        if (color.equals("W")) { // 흰색으로 시작하는 경우
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    result[i][j] = white;
                    white = !white;
                }
                white = !white;
            }
        } else {
            for (int i = 0; i < 8; i++) {
                white = !white;
                for (int j = 0; j < 8; j++) {
                    result[i][j] = white;
                    white = !white;
                }
            }
        }
        return result;
    }
}