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

제목 : 체스판 다시 칠하기

---

문제

지민이는 자신의 저택에서 MN 개의 단위 정사각형으로 나누어져 있는 M x N 크기의 보드를 찾았다.

어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다.

지민이는 이 보드를 잘라서 8 x 8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다.

구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고,

변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다.

따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지 뿐이다.

하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8 x 8 크기의 체스판으로 잘라낸 후에,

몇 개의 정사각형을 다시 칠해야 겠다고 생각했다.

당연히 8 x 8 크기는 아무데서나 골라도 된다.

지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N 과 M 이 주어진다.

N 과 M 은 8 보다 크거나 같고, 50 보다 작거나 같은 자연수이다. (8 <= N, M <= 50)

둘째 줄 부터 N 개의 줄에는 보드의 각 행의 상태가 주어진다.

B 는 검은색이며, W 는 흰색이다.

출력

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

예제 입력	예제 출력
8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW	1
10 13 BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB	12
8 8 BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB	0
10 10 BBBBBBBBBB BBWBWBWBWB BWBWBWBWBB BBWBWBWBWB BWBWBWBWBB BBWBWBWBWB BWBWBWBWBB BBWBWBWBWB BWBWBWBWBB BBBBBBBBBB	0
8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWWWB BWBWBWBW	2
11 12 BWWBWWBWWBWW BWWBWBBWWBWW WBWWBWBBWWBW BWWBWBBWWBWW WBWWBWBBWWBW BWWBWBBWWBWW WBWWBWBBWWBW BWWBWBWWWBWW WBWWBWBBWWBW BWWBWBBWWBWW WBWWBWBBWWBW	15
9 23 BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBW	31

---

우리는 체스판의 형태가 어떻게 생겼는지 알고 있다.

중간의 정사각형 아무거나 선택한다면, 좌우상하의 색상이 현재 정사각형과 다른 색상을 띈다는 것이다.

하지만, 이러한 규칙만 지켜진다면, "하얀색" 이던, "검은색" 이던 상관없는 것이다.

위의 규칙을 지키는 평범한 체스판을 만들기 위해서, 8 x 8 크기의 체스판을 만든다고 한다.

입력 값은 열 (column), 행(row) 둘 다 최소 8 길이 이상을 가지고 있다.

상상해 보면 된다. - 8 x 8 크기의 절삭기가 있으며, 정확히 잘라서 다시 색칠한다는 느낌으로.

그런데, 여기서 문제가 하나 있다.

그 문제는 색상 2 가지가 전부 가능하다는 것이다.

그 말은,

1. 검은색 타일 시작 일 때
2. 하얀색 타일 시작 일 때

이렇게 두 가지의 경우로 나누어진다.

W	B	W	B
B	W	B	W
W	B	W	B
B	W	B	W
W	B	W	B
B	W	B	W

OR

B	W	B	W
W	B	W	B
B	W	B	W
W	B	W	B
B	W	B	W
W	B	W	B

체스판을 만들 수 있는 경우는 위와 같은 2 개이며,

주어진 형태 (MN) 크기에서 랜덤으로 색상이 배치된다.

즉, 위 2 개의 경우를 대입하여 비교해야 한다.

그렇다면, 최소값을 찾는 기준이 무엇인지 여기서 짚고 넘어가자.

1. 8 x 8 크기로 자를 row, column 의 위치
2. W 시작인지, B 시작인지.

문제를 풀 수 있는 2 가지 방식

나도 처음에 이 문제를 접했을 때, 단순한 Brute Force(모든 경우의 수 대입) 을 고려했다.

그런데, 이제 와서 살펴보니 DP (Dynamic Programming) 방식도 가능하다는 것을 눈치챘다.

따라서, 이번 풀이에는 2 가지 풀이 방식을 작성 해 보려고 한다.

Answer 1 - Brute Force (가능한 모든 경우의 수 대입)

우리는 최소값을 찾기 위해 모든 수를 넣을 것이다.

그런데, 알고리즘에서 자주 나오는 "시간 복잡도" 를 짚고 넘어갈 필요가 있다고 생각한다.

그렇다. 우리는 이 문제를 풀이 위해 모든 조건을 Iterable 하게 (반복행동) 하게 만들 건데,

이 문제의 추상적인 시간 복잡도는 N 의 몇 제곱일까?

이 문제는 N ^ 3 문제이다. 즉, 어마어마한 반복이 수행 될 것이라는 것이다.

단순히 하얀색, 검은색 자체만 신경쓰니, (N ^ 2) x 2 가 아닌가? 할 수 있겠지만,

맞기는 하다. 그러나, 색상이 몇 개가 아니라면 어떻게 되는가? 바로 N ^ 3 이 되는 것이다.

그래서 내가 이 문제를 풀이하기 위해 살펴보던 도중, DP 의 풀이 방식도 떠올랐던 것이다.

거두절미하고 문제를 풀어보자.

import java.util.*;
import java.io.*;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 입력될 보드의 상태를 저장할 2차원 배열 생성.
        char[][] inputBoard = new char[N][M];

        // 하얀색 시작 보드
        char[][] white = new char[8][8];
        // 검은색 시작 보드
        char[][] black = new char[8][8];

        // 열과 행의 인덱스 합이 짝수인지, 홀수인지에 따라서, 간단히 흑백을 나눌수가 있단 것을 관찰 후 알게 되었다!
        for(int i = 0; i < 8; i++) {
            for(int j = 0; j < 8; j++) {
                if((i + j) % 2 == 0) {
                    white[i][j] = 'W';
                    black[i][j] = 'B';
                } else {
                    white[i][j] = 'B';
                    black[i][j] = 'W';
                }
            }
        }

        // 초기화 시작 
        for(int i = 0; i < N; i++) {
            String row = br.readLine();
            for(int j = 0; j < M; j++) {
                inputBoard[i][j] = row.charAt(j);
            }
        }

        // 최소값 초기화.
        int minDiff = Integer.MAX_VALUE;

        // 8 x 8 칸을 잘랐을 때, 차이 최소값을 구한다.
        for(int i = 0; i < inputBoard.length - 7; i++) {
            for(int j = 0; j < inputBoard[0].length - 7; j++) {
                // 현재 점으로부터 하얀색, 검은색 보드와의 최소 차이 값을 가져온다.
                int min = getMinDiff(inputBoard, white, black, i, j);

                // 최소값 갱신.
                minDiff = min < minDiff ? min : minDiff;
            }
        }

        System.out.println(minDiff);
    }

    // 하얀색과 검은색 시작 보드 중 차이가 가장 작은 수를 반환한다.
    static int getMinDiff(char[][] inputBoard, char[][] whiteBoard, char[][] blackBoard, int y, int x) {
        int whiteDiff = 0;
        int blackDiff = 0;

        // 시작점으로부터 8 줄 비교
        for(int i = y; i < y + 8; i++) {
            // 시작점으로부터 8 열 비교
            for(int j = x; j < x + 8; j++) {
                // 주어진 보드의 색상을 가져온다.
                char currColor = inputBoard[i][j];

                // 하얀색 시작 보드의 색상 (0, 0 부터 시작해야 한다.)
                char whiteColor = whiteBoard[i - y][j - x];
                // 검은색 시작 보드의 색상 (이것도 0, 0 부터 시작해야 한다.)
                char blackColor = blackBoard[i - y][j - x];

                // 하얀색 보드와의 차이를 적층하자.
                if(currColor != whiteColor) {
                    whiteDiff++;
                }

                // 검은색 보드와의 차이를 적층.
                if(currColor != blackColor) {
                    blackDiff++;
                }
            }
        }

        // 하얀색, 검은색 보드 차이 중 작은 수를 반환한다.
        return whiteDiff < blackDiff ? whiteDiff : blackDiff;
    }
}

Answer 2 - DP 방식

만약 "단계별로 풀어보기" 방식으로 풀고 있는 독자라면, 이제 내가 DP 방식으로 풀이하게 되는 방식을

살펴보며, 어떠한 방식으로 다이나믹 프로그래밍이 이루어질 수 있는지 흐름으로 보길 권한다.(권합니다.)

사실 다이나믹 프로그래밍이라는 것 자체가 많은 알고리즘을 포괄하고 있기 때문에,

현재로서는, "배열에 특정 값을 기억하고, 이를 재사용한다" 라고 이해하면 된다.

DP 방식을 고려하게 된 계기

이 문제의 분류는 엄연히 "브루트포스" 로 분류되어 있다.

하지만, 이 문제의 풀이 방식은 시간 복잡도가 N^3 이다.

물론, 검은색과 하얀색 2 개의 상황만 파악하여 최소값을 반환하면 되기에,

주어진 조건으로는 그리 큰 시간 복잡도를 가지고 있지는 않다.

그러나, 만약에 처음 주어지는 체스판의 크기가 만약 100,000 줄, 100,000 이 된다면,

벌써 우리가 반복문을 사용하여 최소값을 구해야 할 시도는 10,000,000,000 (100 억) 이다.

벌써부터 N ^ 2 를 고려하더라도, 100 억이라는 최대 시간 복잡도가 나오게 되는 것이다.

이를 방지하기 위해, 모든 입력을 받은 후, 다시 해당 입력에 대해서 계산하는 것이 아니라,

"입력을 받으면서 결과를 계산하는 법" 을 사용할 수 있다.

다만, 입력값에 해당하는 최소값을 기억해야 하기 때문에, 동일한 크기의 배열을 생성 해 주어야 한다.

import java.util.*;
import java.io.*;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력 될 row 의 수
        int N = Integer.parseInt(st.nextToken());
        // 입력 될 column 의 수
        int M = Integer.parseInt(st.nextToken());

        // 하얀색 시작 보드와의 차이를 기억할 배열
        int[][] whiteDiff = new int[N][M];
        // 검은색 시작 보드와의 차이를 기억할 배열
        int[][] blackDiff = new int[N][M];

        // 0번째 줄, 0번째 열 보드 색상.
        char whiteBoardColor = 'W';
        char blackBoardColor = 'B';

        // 첫 줄 입력
        String currLine = br.readLine();

        int whiteMin = Integer.MAX_VALUE;
        int blackMin = Integer.MAX_VALUE;


        // 첫 번째 줄 초기화.
        for(int col = 0; col < M; col++) {
            if(col > 0) {
                whiteDiff[0][col] = whiteDiff[0][col - 1];
                blackDiff[0][col] = blackDiff[0][col - 1];
            }

            if(col % 2 == 0) {
                whiteBoardColor = 'W';
                blackBoardColor = 'B';
            } else {
                whiteBoardColor = 'B';
                blackBoardColor = 'W';
            }

            char currColor = currLine.charAt(col);

            if(whiteBoardColor != currColor)
                whiteDiff[0][col]++;
            if(blackBoardColor != currColor)
                blackDiff[0][col]++;
        }

        // i = row,  j = column
        for(int i = 1; i < N; i++) {
            currLine = br.readLine();

            for(int j = 0; j < M; j++) {
                char currColor = currLine.charAt(j);

                whiteBoardColor = 'I';
                blackBoardColor = 'I';

                if((i + j) % 2 == 0) {
                    whiteBoardColor = 'W';
                    blackBoardColor = 'B';
                } else {
                    whiteBoardColor = 'B';
                    blackBoardColor = 'W';
                }

                // 1 번째 열 이라면.
                if(j == 0) {
                    whiteDiff[i][j] = whiteDiff[i - 1][j];
                    blackDiff[i][j] = blackDiff[i - 1][j];
                } else {
                    // 도형으로 생각해보자. - 이전 열 까지의 직사각형을 더한다.
                    whiteDiff[i][j] += whiteDiff[i][j - 1];
                    blackDiff[i][j] += blackDiff[i][j - 1];

                    // 바로 위에 해당하는 "한 줄의" 차이들을 더한다.
                    whiteDiff[i][j] += (whiteDiff[i - 1][j] - whiteDiff[i - 1][j - 1]);
                    blackDiff[i][j] += (blackDiff[i - 1][j] - blackDiff[i - 1][j - 1]);
                }

                // 만약 현재 색상과, 하얀색 시작 보드와의 색상이 다르다면,
                // 현재 줄의 하얀색 시작 보드 차이를 적층한다.
                if(currColor != whiteBoardColor) {
                    whiteDiff[i][j]++;
                }

                // 검은색 보드와의 색상이 다르다면, 현재 줄의 검은색 보드 차이를 적층한다.
                if(currColor != blackBoardColor) {
                    blackDiff[i][j]++;
                }


                // 마지막으로, 8 x 8 체스판을 수용할 수 있을 때, 최소값을 계산한다.
                if(i >= 7 && j >= 7) {
                    int eraseRow = i - 8;
                    int eraseCol = j - 8;

                    // 윗 부분 차이점 가져오기
                    int upperWhiteDiff = 0;
                    int upperBlackDiff = 0;

                    // 만약 자를 윗 부분이 있다면, 그 때 계산.
                    if(eraseRow >= 0) {
                        upperWhiteDiff = whiteDiff[eraseRow][j];
                        upperBlackDiff = blackDiff[eraseRow][j];
                    }

                    // 정확히 왼쪽의 차이점을 추출
                    int rightWhiteDiff = 0;
                    int rightBlackDiff = 0;

                    // 자를 윗 부분과 왼쪽 부분이 없을 때. (정확히 8 x 8)
                    if(eraseRow < 0 && eraseCol < 0) {
                        rightWhiteDiff = 0;
                        rightBlackDiff = 0;
                    } else if(eraseRow < 0) { // 자를 윗 부분만 없을 때.
                        rightWhiteDiff = whiteDiff[i][eraseCol];
                        rightBlackDiff = blackDiff[i][eraseCol];
                    } else if(eraseCol < 0) { // 자를 왼쪽 부분이 없을 때.
                        rightWhiteDiff = 0;
                        rightBlackDiff = 0;
                    } else { // 윗 부분, 왼쪽 부분 둘 다 잘라야 할 때.
                        rightWhiteDiff = whiteDiff[i][eraseCol] - whiteDiff[eraseRow][eraseCol];
                        rightBlackDiff = blackDiff[i][eraseCol] - blackDiff[eraseRow][eraseCol];
                    }

                    // 현재 위치에서 8 x 8 크기로 잘랐을 때, 하얀색, 검은색 보드와의 차이를 구했다.
                    int totalWhiteDiff = whiteDiff[i][j] - upperWhiteDiff - rightWhiteDiff;
                    int totalBlackDiff = blackDiff[i][j] - upperBlackDiff - rightBlackDiff;

                    // 보드 별 최소값 갱신.
                    whiteMin = whiteMin > totalWhiteDiff ? totalWhiteDiff : whiteMin;
                    blackMin = blackMin > totalBlackDiff ? totalBlackDiff : blackMin;

                }
            }
        }

        int totalMin = whiteMin < blackMin ? whiteMin : blackMin;

        System.out.println(totalMin);
    }
}

이러한 방식으로 풀 수도 있지만,

솔직히 말해서 코드가 지저분 할 수 밖에 없다.

"이러한 방식으로도 풀 수 있구나" 하고 살펴보면 좋을 것 같다.