[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 영역 중 최소값을 갱신하여 출력한다.

💻 전체 코드

package org.example;

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

public class Main {
    static char[][] board;

    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());

        board = new char[n][m];

        // 보드 입력
        for(int i=0; i<n; i++){
            String line = br.readLine();
            for(int j=0; j<m; j++){
                board[i][j] = line.charAt(j);
            }
        }

        int min = Integer.MAX_VALUE;
        // 모든 8 x 8 검사
        for(int i=0; i<=n-8; i++){
            for(int j=0; j<=m-8; j++){
                int result = minPaintingCnt(i, j);
                min = Math.min(min, result);
            }
        }
        System.out.println(min);
    }

    public static int minPaintingCnt(int x, int y){
        int w_diff = 0;
        int b_diff = 0;

        for(int i=0; i<8; i++){
            for(int j=0; j<8; j++){
                char current = board[x + i][y + j];
                char startW = ((i + j) % 2 == 0) ? 'W' : 'B';
                char startB = ((i + j) % 2 == 0) ? 'B' : 'W';

                if (current != startW) w_cnt++;
                if (current != startB) b_cnt++;

            }
        }
        return Math.min(w_diff, b_diff);
    }
}

💭 메타인지

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

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