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

---

https://www.acmicpc.net/problem/1018

---

📌 문제

문제 유형

• 구현
• 브루트포스

문제 설명

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

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다.

따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다.

당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입출력 예시

입력

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWWWB
BWBWBWBW

출력

2

🔍 문제 풀이

① 8×8 보드를 모든 위치에서 검사한다.

예를 들어, 10×13이라면 (0,0)부터 시작해서 (2,5)까지 총 (n-8+1) × (m-8+1)개의 경우를 검사

② (i+j)의 짝/홀수에 따라 바둑판 색 결정 (‘W’로 시작 vs ‘B’로 시작)

• 예를 들어 i+j가 짝수인 칸은 첫 색(W 또는 B)로 칠해져 있어야 하고, 홀수인 칸은 반대 색으로 칠해져야 한다.
• 시작 색이 ‘W’일 경우와 ‘B’일 경우 두 가지 모두 고려해야 한다. (이 조건을 인지하지 못하여 헤맸었다.)
• 하나는 ‘W’로 시작했을 때 바뀌어야 하는 칸 수(w_cnt)와, ‘B’로 시작했을 때 바뀌어야 하는 칸 수(b_cnt)를 세면 된다.

③ 모든 8×8 영역 중 최솟값을 갱신하여 출력한다.

💻 전체 코드

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

public class Main {
    static int n, m;
    static char[][] board;

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

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new char[n][m];


        // 입력 받기
        for(int i=0; i<n; i++){
            String s = br.readLine();
            for(int j=0; j<m; j++){
                board[i][j] = s.charAt(j);

            }
        }

        // 보드판 자르기
        int min = Integer.MAX_VALUE;
        for(int i=0; i<=n-8; i++) { // 이게 헷갈림 i<=n-8 범위
            for(int j=0; j<=m-8; j++){
                int result = solved(i, j);
                min = Math.min(min,result);
            }
        }
        System.out.println(min);

        // 입력을 받고, 보드판을 8x8로 자른걸 solved 함수에 넘겨주기.
        // solved 함수는 보드판을 순회하며 Math.min(w_cnt, b_cnt) 최소 개수를 찾는다.

    }
    public static int solved(int x, int y){
        int w_cnt = 0;
        int b_cnt = 0;

        for(int i=x; i<x+8; i++){

            for(int j=y; j<y+8; j++){
                char current = board[i][j];
                if((i+j) % 2 == 0){ // 첫 색상이 와야할 칸
                    // 첫 색상이 W일 때
                    if(current != 'W') w_cnt++;
                    if(current != 'B') b_cnt++;
                }else{
                    // 첫 색상이 B일 때
                    if (current != 'B') w_cnt++;
                    if (current != 'W') b_cnt++;
                }
            }
        }
        return Math.min(w_cnt, b_cnt);

    }
}

💭 메타인지

8×8 크기로 슬라이스할 때, i <= n - 8, j <= m - 8과 같이 조건 설정을 하지 못해 디버깅에 시간을 소모했다.

체스판의 시작 색이 ‘W’ 또는 ‘B’ 두 가지 경우라는 것을 처음에 명확히 이해하지 못해서 (i + j) % 2 조건으로 비교하는 로직을 검색을 통해 알게 되었다.