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

문제

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

 

---

문제 개요

M x N 크기의 보드에서 8x8 크기의 체스판을 만들기 위해 다시 칠해야 하는 최소한의 칸 수를 구하는 문제입니다. 체스판은 흑백이 번갈아 칠해진 패턴으로 이루어져 있어야 하며, 보드의 임의의 8x8 부분을 잘라냈을 때 그 부분이 체스판 패턴을 따르지 않는다면, 일부 칸을 다시 칠해야 합니다. 이때, 좌상단이 흰색 또는 검은색으로 시작하는 두 가지 경우에 대해 각각의 칸을 얼마나 다시 칠해야 하는지 계산하고, 그중 최소 값을 구하는 것이 목표입니다.

 

접근 방법

1. 체스판 규칙:
   • 체스판은 검은색과 흰색이 번갈아 가면서 칠해져 있습니다. 시작점이 흰색인 경우와 검은색인 경우, 두 가지로 나누어 계산할 수 있습니다.
2. 체스판 비교:
   • 8x8 크기로 보드를 자른 후, 두 가지 색칠 방식에 대해 얼마나 차이가 나는지 계산합니다. 다시 칠해야 하는 칸의 수를 세어 가장 적은 경우를 선택합니다.
3. 브루트포스:
   • 입력된 보드에서 8x8 크기의 체스판을 잘라낼 수 있는 모든 위치를 탐색하며, 각각의 8x8 영역을 두 가지 색칠 방식과 비교하여 다시 칠해야 하는 칸의 최소 개수를 계산합니다.

 

import java.io.*;
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 N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        char[][] board = new char[N][M];
        
        // 보드 입력 받기
        for (int i = 0; i < N; i++) {
            board[i] = br.readLine().toCharArray();
        }
        
        int minPaint = Integer.MAX_VALUE;
        
        // 8x8 체스판을 자를 수 있는 모든 위치에서 체크
        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                minPaint = Math.min(minPaint, getMinRepaints(board, i, j));
            }
        }
        
        System.out.println(minPaint);
    }
    
    // 8x8 영역에서 다시 칠해야 할 최소 칸 수를 계산하는 함수
    public static int getMinRepaints(char[][] board, int startRow, int startCol) {
        int count1 = 0; // 첫 번째 칸이 'W'로 시작하는 경우
        int count2 = 0; // 첫 번째 칸이 'B'로 시작하는 경우
        
        char[] pattern = {'W', 'B'}; // 두 색의 패턴
        
        // 8x8 크기 탐색
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                char expectedChar1 = pattern[(i + j) % 2]; // 첫 칸이 'W'로 시작할 때 예상되는 값
                char expectedChar2 = pattern[(i + j + 1) % 2]; // 첫 칸이 'B'로 시작할 때 예상되는 값
                
                if (board[startRow + i][startCol + j] != expectedChar1) {
                    count1++;
                }
                if (board[startRow + i][startCol + j] != expectedChar2) {
                    count2++;
                }
            }
        }
        
        return Math.min(count1, count2); // 두 경우 중 더 적은 값을 반환
    }
}