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

문제

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

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

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

---

입력

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

---

출력

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

---

예제 입력 1 

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

 

예제 출력 1 

1

 

 

내가 푼 코드

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

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 row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());
		
        // WBWBWBWB 라인별로 읽어서 String 배열에 담음
        String[] board = new String[row];

        for (int i = 0; i < row; i++) {
            board[i] = br.readLine();
        }

        int sol = Integer.MAX_VALUE;
        // row-8 : startIdx의 최대값을 row-8로 해줌
        // col-8 : endIdx의 최대값을 col-8로 해줌
        for (int i=0; i<=row-8; i++) {
            for (int j=0; j<=col-8; j++) {
                int curSol = solution(i, j, board);
                if (sol > curSol) sol = curSol;
            }
        }

        System.out.println(sol);
    }

    private static int solution(int startRow, int startCol, String[] board) {
        // 화이트색 시작점으로 찾을것임
        String[] checkBoard = {"WBWBWBWB", "BWBWBWBW"};
        int cnt = 0;
        for (int i=0; i<8; i++) {
            int curRow = startRow + i;
            for (int j=0; j<8; j++) {
                int curCol = startCol + j;
                // curRow % 2
                // 0, 1, 0, 1, 0, 1 ...
                if (board[curRow].charAt(curCol) != checkBoard[curRow%2].charAt(j)) cnt++;

            }
        }
        return Math.min(cnt, 64-cnt);

    }
}

 

해당 문제는 브루트포스인데 나는 못풀겠어서 유튜브의 동영상을 보고 이해했다.

 

푸는 방법

 

우선 8 x 8 총 64개에서 체스판 처럼 색을 W, B로 바꿔야하는 최소값을 구해야한다.

나는 이중배열을 만들어서 한 글자씩 읽은 다음 그 글자의 상하좌우를 비교해가면서 바꿔야하는 값을 구하려고 했는데

그렇게 되면 값이 행과 열이 0인 경우 행과 열이 N과 M보다 큰경우 등 여러가지 경우의 수를 다 구해야하고 코드짜기가 쉽지 않았다.

 

그래서 참고하게된 유튜브 영상을 보니 체스판에서 'W'로 시작할때와 'B'로 시작할때 2가지의 경우에 수를 구한다음 작은 값을 선택해줘야하는데 아래와 같다.

블랙 체스판의 변경할 최소 값 +  화이트 체스판의 변경할 최소 값 = 체스판의 수 ( 64 )

 

따라서, 블랙으로 시작하는 경우만 구한 다음 64 - 최소값을 하면 화이트체스판으로 시작한 경우의 최소값이 나오기 때문에 둘중 하나의 경우만 가지고 값을 구하면 됨

 

 

int sol = Integer.MAX_VALUE;
for (int i=0; i<=row-8; i++) {
    for (int j=0; j<=col-8; j++) {
        int curSol = solution(i, j, board);
        if (sol > curSol) sol = curSol;
    }
}

이 코드에서 row - 8과 col - 8로 해준것은?

N과 M은 무조건 8이상의 수가 들어올 것이며, 이때 i와 j는 체스판을 시작할 startRowIdx와 startColIdx 이기 때문에 그 값은 N - 8 , M - 8 보다 클수없다.

예를 들어 N = 8이고, M = 8이면 체스판은 0~7까지 행과 열이 존재하기 때문에 for문은 i=0이고, j=0인 경우만 반복된다.

i = 1인 경우 1~8 행까지 반복해야하는데 8행이 존재하지 않음

j도 마찬가지임

 

 

// 화이트색 시작점으로 찾을것임
String[] checkBoard = {"WBWBWBWB", "BWBWBWBW"};
int cnt = 0;
for (int i=0; i<8; i++) {
    int curRow = startRow + i;
    for (int j=0; j<8; j++) {
        int curCol = startCol + j;
        // curRow % 2
        // 0, 1, 0, 1, 0, 1 ...
        if (board[curRow].charAt(curCol) != checkBoard[curRow%2].charAt(j)) cnt++;

    }
}

이 코드에서 curRow와 curCol을 따로 준것은?

예를 들어 startRow = 0, startCol = 0인 경우

curRow = 0 + 0, 0 +1, 0 + 2, ... 0 + 7까지 반복됨

curCol = 0 + 0, 0 +1, 0 + 2, ... 0 + 7까지 반복됨

 

이 코드에서 checkBoard[curRow % 2] 는?

배열에 0과 1인덱스만 존재하고 계속 반복되어야 하기 때문에 해당 row % 2를 해주면 0, 1, 0, 1, 0, 1 이 반복됨

 

 

이 코드에서 charAt(curCol)과 charAt[j] 는?

boar[] 의 경우 열의 인덱스가 8까지 존재하지 않고 더 많을 수도 있음 (M의 값이기 때문에)

그러나 checkBoard[] 배열의 경우 WBWBWBWB 와 같이 8자리가 고정되어있기 때문에 curRow로 하면 startRow + i 이기 때문에 7을 넘어갈수도 있어서 j로 세팅해줌

 

 

해당 문제풀이 참고한 유튜브 주소:

https://www.youtube.com/watch?v=QQUb4b6iWSw